بدخواه پویان

محدودیت ز مان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بدخواه، بدِ پویان را میخواهد. او میداند که اگر پایِ یک عدد زوج مانند $p$ در میان باشد، پویان عاشق اعدادی است که باقیمانده شان بر $p$ بین $\frac p 2+1$ تا $p-1$ است. بنابراین بدخواه دنبال اعدادیست که باقیمانده‌شان بر $p$ بین $0$ تا $\frac p 2$ است.

به بدخواه یک عدد داده شده‌است(آن را $d$ می‌نامیم). حال برای او سوالی پیش آمده و آن هم این است کوچکترین عدد طبیعی که مضرب $d$ است و باقیمانده‌اش بر $p$ بین $0$ تا $\frac p 2$ است، چیست؟

ورودی🔗

سطر اول ورودی شامل اعداد $p$ و $d$ است که $d$ نشان‌دهنده‌ی عددی است که به بدخواه داده شده تا کوچکترین مضربش را که شرط داده شده را دارد، پیدا کند. دقت کنید که عدد $p$ زوج است!

$2 \le p \le 100$ $1 \le d \le 1000$

خروجی🔗

تنها سطر خروجی باید شامل کوچکترین مضرب $d$ باشد که باقیمانده‌اش بر $p$ بین $0$ تا $\frac p 2$ است.

مثال🔗

ورودی نمونه🔗

8 7

خروجی نمونه🔗

توضیح: باقیمانده 7 بر 8، 7 است. باقیمانده 7+7=14 بر 8، 6 است. باقیمانده 7+7+7=21 بر 8، 5 است. و بالاخره باقیمانده 7+7+7+7=28 بر 8، 4 است. پس 28 کوچکترین مضرب 7 است که باقیمانده اش بر 8 بین 0 تا 4 می‌باشد.

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بد خواه، بدِ مردم را میخواهد. از این رو بر آن شده است که مردم را سرگرم کند و وقتشان را تلف کند تا به کار های مهم زندگی نرسند. او ابتدا مردم را به یک اتاق دعوت می‌کند. سپس کیسه ای را با $m$ توپ سیاه و $n$ توپ سفید پر میکند. سپس از شخصی میخواهد تا دو توپ از کیسه بیرون بیاورد. اگر دو توپ هم رنگ بودند، یک توپ سفید جدید در داخل کیسه بیاندازد و اگر همرنگ نبودند، یک توپ سیاه جدید داخل کیسه بیاندازد. سپس دو توپ خارج شده را دور بیاندازد. آن شخص باید اینقدر این کار را تکرار کند تا دقیقاً یک توپ داخل کیسه باقی بماند. بعد از اینکه بد خواه از کسی خواهش کرد که او این کار را انجام دهد، قبل از این که آن شخص شروع به انجام کار کند بدخواه از آن اتاق بیرون رفته و وقتی که دقیقا یک توپ در کیسه باقی مانده بود به اتاق برمیگردد. دقت کنید که بدخواه از ترتیب بیرون آوردن توپ‌ها بی اطلاع است و تنها $n$ و $m$ را میداند. از آنجایی که بدخواه دنبال سرگرم کردن مردم است، میخواهد رنگ توپ داخل کیسه را پیش‌بینی کند. اما از آنجایی که ذاتاً آدم بی‌هنریست، توانایی انجام این کار را ندارد. از این رو بر آن شده است که از شما کمک بگیرد و از شما می‌خواهد که رنگ توپ را فقط با دانستن $n$ و $m$ برای او پیش بینی کنید یا به او بگویید امکان پیش‌بینی وجود ندارد زیرا امکان دارد توپ باقی‌مانده سفید یا سیاه (بسته به ترتیب بیرون آوردن توپ‌ها) باشد تا او بتواند با انجام حرکات موزون مردم را سرگرم کند تا ناتوانی او در پیش‌بینی را فراموش کنند. # ورودی سطر اول ورودی شامل دو عدد $m$ و $n$ است که به ترتیب نشان دهنده‌ ی تعداد توپ‌های سیاه و تعداد توپ‌های سفید اند. $$ 1 \le m,n \le 1000\ 000\ 000$$ # خروجی تنها سطر خروجی باید شامل یک کلمه باشد: + $white$ : به معنای اینکه توپ آخر سفید است. + $black$ : به معنای اینکه توپ آخر سیاه است. + $no prediction$ : به معنای اینکه امکان پیش‌بینی وجود ندارد. # مثال ## ورودی نمونه ۱ ``` 2 2 ``` ## خروجی نمونه ۱ ``` white ``` ## ورودی نمونه ۲ ``` 3 6 ``` ## خروجی نمونه ۲ ``` black ```

بدخواه مردم

محدودیت زمان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بد خواه، بدِ مردم را میخواهد. از این رو بر آن شده است که مردم را سرگرم کند و وقتشان را تلف کند تا به کار های مهم زندگی نرسند. او ابتدا مردم را به یک اتاق دعوت می‌کند. سپس کیسه ای را با $m$ توپ سیاه و $n$ توپ سفید پر میکند. سپس از شخصی میخواهد تا دو توپ از کیسه بیرون بیاورد. اگر دو توپ هم رنگ بودند، یک توپ سفید جدید در داخل کیسه بیاندازد و اگر همرنگ نبودند، یک توپ سیاه جدید داخل کیسه بیاندازد. سپس دو توپ خارج شده را دور بیاندازد. آن شخص باید اینقدر این کار را تکرار کند تا دقیقاً یک توپ داخل کیسه باقی بماند. بعد از اینکه بد خواه از کسی خواهش کرد که او این کار را انجام دهد، قبل از این که آن شخص شروع به انجام کار کند بدخواه از آن اتاق بیرون رفته و وقتی که دقیقا یک توپ در کیسه باقی مانده بود به اتاق برمیگردد. دقت کنید که بدخواه از ترتیب بیرون آوردن توپ‌ها بی اطلاع است و تنها $n$ و $m$ را میداند. از آنجایی که بدخواه دنبال سرگرم کردن مردم است، میخواهد رنگ توپ داخل کیسه را پیش‌بینی کند. اما از آنجایی که ذاتاً آدم بی‌هنریست، توانایی انجام این کار را ندارد. از این رو بر آن شده است که از شما کمک بگیرد و از شما می‌خواهد که رنگ توپ را فقط با دانستن $n$ و $m$ برای او پیش بینی کنید یا به او بگویید امکان پیش‌بینی وجود ندارد زیرا امکان دارد توپ باقی‌مانده سفید یا سیاه (بسته به ترتیب بیرون آوردن توپ‌ها) باشد تا او بتواند با انجام حرکات موزون مردم را سرگرم کند تا ناتوانی او در پیش‌بینی را فراموش کنند.

ورودی🔗

سطر اول ورودی شامل دو عدد $m$ و $n$ است که به ترتیب نشان دهنده‌ ی تعداد توپ‌های سیاه و تعداد توپ‌های سفید اند. $1 \le m,n \le 1000\ 000\ 000$

خروجی🔗

تنها سطر خروجی باید شامل یک کلمه باشد:

$white$ : به معنای اینکه توپ آخر سفید است.
$black$ : به معنای اینکه توپ آخر سیاه است.
$no prediction$ : به معنای اینکه امکان پیش‌بینی وجود ندارد.

مثال🔗

ورودی نمونه ۱🔗

2 2

خروجی نمونه ۱🔗

white

ورودی نمونه ۲🔗

3 6

خروجی نمونه ۲🔗

black

+ محدودیت ز مان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بدخواه، بدِ شما را میخواهد. او میداند که شما از خواندن داستان‌های جذاب ما!! لذت میبرید. از این رو بر آن شد که سوالی را بر ما تحمیل کند که نوشتن داستانی جذاب برای آن، کار سختی باشد. پس با مقدمه به سراغ سوال میرویم: یک جدول $n \times n$ داریم. در هر خانه ی آن یا عدد $0$ است یا عدد $1$. شما باید با کمترین حرکت کاری کنید که تمام خانه‌هایی که در آنها عدد $1$ نوشته‌شده‌است، یا روی قطر اصلی جدول باشند و یا زیر آن. شما در هر حرکت می‌توانید دو سطر مجاور را با هم جابه‌جا کنید. قطر اصلی:برای مثال 1 ها در این جدول $5 \times 5$ قطر اصلی را تشکیل می‌دهند: 10000 01000 00100 00010 00001 **در ورودی‌های داده شده، تضمین میشود همیشه میتوان به هدف گفته شده رسید.** # ورودی در سطر اول عدد $n$ آمده که نشان‌دهنده تعداد سطرهای جدول است. در $n$ سطر بعدی جدول آمده است. $$1 \le n \le 40$$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که نشان‌دهنده‌ی کمترین تعداد حرکت لازم برای این است که تمام یک‌ها یا روی قطر اصلی و یا زیر آن باشند. # مثال ## ورودی نمونه ۱ ``` 2 10 11 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 3 001 100 010 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 4 1110 1100 1100 1000 ``` ## خروجی نمونه ۳ ``` 4 ``` توضیح نمونه ۲: ابتدا سطر اول(از بالا) را با دوم و سپس سطر دوم را با سوم عوض میکنیم. شکل نهایی چنین است: ``` 100 010 001 ``` توضیح نمونه ۳: به ترتیب جابه‌جایی‌ها(سطر ها از بالا): 4 با 3، 3 با 2، 2 با 1، 3 با 2 شکل نهایی: ``` 1000 1100 1110 1100 ```

بدخواه شما

محدودیت ز مان: ۰.۵ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بدخواه، بدِ شما را میخواهد. او میداند که شما از خواندن داستان‌های جذاب ما!! لذت میبرید. از این رو بر آن شد که سوالی را بر ما تحمیل کند که نوشتن داستانی جذاب برای آن، کار سختی باشد. پس با مقدمه به سراغ سوال میرویم:

یک جدول $n \times n$ داریم. در هر خانه ی آن یا عدد $0$ است یا عدد $1$ . شما باید با کمترین حرکت کاری کنید که تمام خانه‌هایی که در آنها عدد $1$ نوشته‌شده‌است، یا روی قطر اصلی جدول باشند و یا زیر آن. شما در هر حرکت می‌توانید دو سطر مجاور را با هم جابه‌جا کنید.

قطر اصلی:برای مثال 1 ها در این جدول $5 \times 5$ قطر اصلی را تشکیل می‌دهند:

در ورودی‌های داده شده، تضمین میشود همیشه میتوان به هدف گفته شده رسید.

ورودی🔗

در سطر اول عدد $n$ آمده که نشان‌دهنده تعداد سطرهای جدول است. در $n$ سطر بعدی جدول آمده است.

$1 \le n \le 40$

خروجی🔗

تنها سطر خروجی باید شامل یک عدد باشد که نشان‌دهنده‌ی کمترین تعداد حرکت لازم برای این است که تمام یک‌ها یا روی قطر اصلی و یا زیر آن باشند.

مثال🔗

ورودی نمونه ۱🔗

2
10
11

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

توضیح نمونه ۲: ابتدا سطر اول(از بالا) را با دوم و سپس سطر دوم را با سوم عوض میکنیم. شکل نهایی چنین است:

100
010
001

توضیح نمونه ۳: به ترتیب جابه‌جایی‌ها(سطر ها از بالا): 4 با 3، 3 با 2، 2 با 1، 3 با 2 شکل نهایی:

+ محدودیت ز مان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بدخواه، بدِ هالو را میخواهد. او میخواهد هالو را به سفر دور کشور ببرد و به ازای هر دور پول بگیرد و اینقدر دور کشور بچرخاند تا هالو سرش گیج برود!!(سر خود بدخواه هم گیج می‌رود ولی همین که سر هالو گیج برود احساس رضایتی به بد‌خواه میدهد که سرگیجه در مقابلش هیچ است) کشور بدخواه و هالو $n$ شهر دارد. بدخواه و هالو در شهر ۱ هستند. بدخواه و هالو اینگونه دور کشور میگردند: در هر بار گردش از شهر ۱ شروع کرده، تمام شهر های کشور به غیر از شهر ۱ را دیده و به شهر ۱ برمیگردند.هر گردش به دور کشور $n$ روز طول میکشد. در هر روز (غیر از روز $n$ ام) آنها یک شهر جدید را که قبلا ندیده بودند، خواهند دید و در روز $n$ ام آنها به شهر اول برمیگردند. به عبارت دیگر هر گردش میشود یک دور که دارای تمام شهر های کشور باشد(دور همیلتونی). برای اینکه آنها از یک شهر به شهر دیگر بروند، باید از جاده‌ی بین این دو شهر استفاده کنند. بین هر دو شهری جاده وجود دارد اما متاسفانه در $k$ تا از جاده ها پلیس وجود دارد که اگر از آن جاده‌ها رد شوند، پلیس بدخواه را به جرم بدخواهی شناسایی و دستگیر میکند. بنابراین بدخواه نمیخواهد که از آن جاده‌ها عبور کنند. نکته ای که وجود دارد این است که هیچ دو گردشی نباید مثل هم باشند؛ یعنی ترتیب دیدن شهر ها در هر دو گردشِ متفاوت، باید متفاوت باشد؛ وگرنه هالو متوجه این میشود که دارند به دور خود میچرخند و سرش را با دست محکم نگه میدارد و دیگر سرش گیج نمیرود و تازه، نامرد دیگر پول هم نمیدهد!! **اگر یکی از گردش ها دقیقاً برعکس دیگری باشد نیز هالو متوجه میشود و چنین اتفاقی می‌افتد.** حالا بدخواه میخواهد بداند که هالو را حداکثر به چند گردش متفاوت میتواند ببرد تا هم سرگیجه‌ی هالو به بیشترین مقدار خود برسد و هم بدخواه بداند که حداکثر چقد پول گیرش می‌آید و هم اینکه بدخواه بتواند وقتش را برای بدخواهی بعدی تنظیم نماید(نظم، کلید موفقیت است)!! اما چون امکان دارد تعداد دور‌های متفاوت زیاد باشد، بدخواه باقیمانده‌ی این عدد را بر $9901$ از شما میخواهد. # ورودی در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است که به ترتیب نشان‌دهنده ی تعداد شهر‌های کشور و تعداد جاده‌هایی است که در آنها پلیس وجود دارد. سپس در $k$ سطر بعدی، در هر سطر، $u_i$ و $v_i$ آمده‌است که نمایانگر شماره‌ی شهر‌هایی است که جاده‌ی بین آنها دارای پلیس است. (یعنی هالو و بدخواه نمیتوانند در طول گردش از شهر با شماره‌ی $u_i$ به $v_i$ و یا برعکس، سفر کنند.) میتوانید فرض کنید که هر جاده حداکثر یک بار در ورودی ظاهر میشود. $$ v_i \neq u_i$$ $$ 3 \le n \le 300 $$ $$ 1 \le v_i, u_i \le n $$ $$ 0 \le k \le 15 $$ # خروجی تنها سطر خروجی باید شامل یک عدد باشد که باقیمانده‌ی حداکثر تعداد دورهایی که بدخواه میتواند هالو را دور کشور بچرخاند، بر $9901$ است. # مثال ## ورودی نمونه ۱ ``` 4 1 1 2 ``` ## خروجی نمونه ۱ ``` 1 ``` توضیح: تنها دوری که وجود دارد، 1-3-2-4 است. ## ورودی نمونه ۲ ``` 8 4 1 2 2 3 4 5 5 6 ``` ## خروجی نمونه ۲ ``` 660 ```

بدخواه هالو

محدودیت ز مان: ۲ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بدخواه، بدِ هالو را میخواهد. او میخواهد هالو را به سفر دور کشور ببرد و به ازای هر دور پول بگیرد و اینقدر دور کشور بچرخاند تا هالو سرش گیج برود!!(سر خود بدخواه هم گیج می‌رود ولی همین که سر هالو گیج برود احساس رضایتی به بد‌خواه میدهد که سرگیجه در مقابلش هیچ است) کشور بدخواه و هالو $n$ شهر دارد. بدخواه و هالو در شهر ۱ هستند. بدخواه و هالو اینگونه دور کشور میگردند:

در هر بار گردش از شهر ۱ شروع کرده، تمام شهر های کشور به غیر از شهر ۱ را دیده و به شهر ۱ برمیگردند.هر گردش به دور کشور $n$ روز طول میکشد. در هر روز (غیر از روز $n$ ام) آنها یک شهر جدید را که قبلا ندیده بودند، خواهند دید و در روز $n$ ام آنها به شهر اول برمیگردند. به عبارت دیگر هر گردش میشود یک دور که دارای تمام شهر های کشور باشد(دور همیلتونی). برای اینکه آنها از یک شهر به شهر دیگر بروند، باید از جاده‌ی بین این دو شهر استفاده کنند. بین هر دو شهری جاده وجود دارد اما متاسفانه در $k$ تا از جاده ها پلیس وجود دارد که اگر از آن جاده‌ها رد شوند، پلیس بدخواه را به جرم بدخواهی شناسایی و دستگیر میکند. بنابراین بدخواه نمیخواهد که از آن جاده‌ها عبور کنند. نکته ای که وجود دارد این است که هیچ دو گردشی نباید مثل هم باشند؛ یعنی ترتیب دیدن شهر ها در هر دو گردشِ متفاوت، باید متفاوت باشد؛ وگرنه هالو متوجه این میشود که دارند به دور خود میچرخند و سرش را با دست محکم نگه میدارد و دیگر سرش گیج نمیرود و تازه، نامرد دیگر پول هم نمیدهد!!

اگر یکی از گردش ها دقیقاً برعکس دیگری باشد نیز هالو متوجه میشود و چنین اتفاقی می‌افتد.

حالا بدخواه میخواهد بداند که هالو را حداکثر به چند گردش متفاوت میتواند ببرد تا هم سرگیجه‌ی هالو به بیشترین مقدار خود برسد و هم بدخواه بداند که حداکثر چقد پول گیرش می‌آید و هم اینکه بدخواه بتواند وقتش را برای بدخواهی بعدی تنظیم نماید(نظم، کلید موفقیت است)!! اما چون امکان دارد تعداد دور‌های متفاوت زیاد باشد، بدخواه باقیمانده‌ی این عدد را بر $9901$ از شما میخواهد.

ورودی🔗

در سطر اول ورودی به ترتیب دو عدد $n$ و $k$ آمده است که به ترتیب نشان‌دهنده ی تعداد شهر‌های کشور و تعداد جاده‌هایی است که در آنها پلیس وجود دارد. سپس در $k$ سطر بعدی، در هر سطر، $u_i$ و $v_i$ آمده‌است که نمایانگر شماره‌ی شهر‌هایی است که جاده‌ی بین آنها دارای پلیس است. (یعنی هالو و بدخواه نمیتوانند در طول گردش از شهر با شماره‌ی $u_i$ به $v_i$ و یا برعکس، سفر کنند.)

میتوانید فرض کنید که هر جاده حداکثر یک بار در ورودی ظاهر میشود.

$v_i \neq u_i$ $3 \le n \le 300$ $1 \le v_i, u_i \le n$ $0 \le k \le 15$

خروجی🔗

تنها سطر خروجی باید شامل یک عدد باشد که باقیمانده‌ی حداکثر تعداد دورهایی که بدخواه میتواند هالو را دور کشور بچرخاند، بر $9901$ است.

مثال🔗

ورودی نمونه ۱🔗

4 1
1 2

خروجی نمونه ۱🔗

توضیح: تنها دوری که وجود دارد، 1-3-2-4 است.

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

+ محدودیت ز مان: ۳ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بدخواه، بدِ جامعه‌ی هنری را هم میخواهد. او تدارک ساخت فیلمی را داده و از $n$ بازیگر مطرح سینما دعوت کرده که در فیلم او بازی کنند. آن‌ها با دیدن فیلمنامه قبول کردند، غافل از نقشه‌هایی که بدخواه برایشان دارد... بدخواه در همان روز اول کار، به سراغ فیلمبرداری صحنه‌ی پایانی میرود - صحنه‌ی دوئل. در این صحنه، این $n$ بازیگر حضور دارند و هریک کسی را در ذهن خود هدف میگیرد، بطوری که هرکس توسط دقیقاً یک نفر هدف‌گرفته شود. بازیگر $i$ـم، بازیگر $p_i$ـم را هدف قرار می‌دهد. در یک لحظه همه‌ی بازیگرها اقدام به شلیک میکنند اما سرعت عکس‌العمل آن‌ها برابر نیست و بازیگر $i$ـم، $t_i$ میلی ثانیه طول میکشد تا ماشه‌ را بچکاند و طعم مرگ‌ را به بازیگر $p_i$ـم بچشاند. بدلیل حرفه‌ای بودن این بازیگرها، هریک دقیقاً به اندازه‌ی مقدار تعیین شده ($t_i$ میلی ثانیه) صبر کرده و سپس بسرعت، هفت‌تیر را بالا آورده و به هدفش ($p_i$ـمین بازیگر) شلیک میکند. این اعمال در زمان اندک انجام میشود.(می‌توان فرض کرد اگر شلیک انجام شود، فرد $p_i$ در لحظه‌ی $t_i$ می‌میرد.) اما بدخواهِ نابکار، در هفت‌تیر این افتخارات ملی، تیر‌های واقعی گمارده و با هر شلیک، یک جوان هنرمند می‌میرد. اگر بازیگر $i$ـم قبل از زمان $t_i$ مرده باشد، در لحظه‌ی $t_i$ شلیکی از طرف این بازیگر صورت نمی‌گیرد. حال بدخواه سناریو‌ را به شما می‌دهد (مقدار $t_i$ها و $p_i$ها) و از شما می‌پرسد که با اجرای این سناریو، در نهایت چند بازیگر زنده می‌مانند. سپس به امید کشته‌های بیشتر، $q$ بار این سناریو را عوض میکند؛ هربار یکی از $t_i$ها را تغییر می‌دهد و پس از هر تغییر نیز از شما می‌پرسد که حال چطور؟! و شما باید تعداد بازیگرهای زنده پس از اجرای این سناریو را به او بگویید. دقت کنید که تغییرات انجام شده باقی می‌مانند؛ بعنوان مثال دومین تغییر روی سناریو ای صورت می‌گیرد که پیش از آن، اولین تغییر روی آن اعمال شده است. # ورودی سطر اول ورودی شامل یک عدد $n$ است که نمایانگر تعداد بازیگرها در سناریوی بدخواه است. در سطر دوم ورودی، $n$ عدد متفاوت آمده است. $i$ـمین عدد $p_i$ است که نمایانگر هدف بازیگر $i$ـم در سناریوی اولیه است. در سطر سوم ورودی، $n$ عدد آمده است. $i$ـمین عدد $t_i$ است که نمایانگر زمان عکس‌العمل بازیگر $i$ـم در سناریوی اولیه است. در سطر چهارم ورودی، یک عدد $q$ آمده است که نمایانگر تعداد تغییرهای سناریو است. سپس در $i$ـمین سطر از $q$ سطر بعدی، دو عدد $b_i$ و $y_i$ آمده است که یعنی در تغییر $i$ـم، زمان عکس‌العمل بازیگر $b_i$ـم در سناریو به $y_i$ تغییر میکند. تضمین می‌شود که همه‌ی اعداد $t_1, t_2, t_3, ..., t_n, y_1, y_2, y_3, ..., y_q$ متفاوت هستند. $$ p_i \neq i $$$$2 \le n \le 200\ 000$$ $$0 \le q \le 200\ 000$$ $$1 \le p_i, b_i \le n$$ $$1 \le y_i, t_i \le 1\ 000\ 000\ 000$$ # خروجی خروجی باید شامل $q + 1$ سطر باشد که هرکدام شامل یک عدد هستند. عدد در سطر اول باید برابر تعداد بازیگرهای زنده درصورت اجرای سناریوی اولیه است. عدد در $i + 1$ـمین سطر باید برابر تعداد بازیگرهای زنده باشد، در صورتی که $i$ تغییر اول روی سناریوی اولیه انجام شود و سناریو را اجرا کنند. # مثال ## ورودی نمونه ``` 4 2 3 4 1 1 3 4 5 3 1 8 2 7 3 6 ``` ## خروجی نمونه ``` 2 2 1 1 ```

بدخواه جامعه‌ی هنری

محدودیت ز مان: ۳ ثانیه
محدودیت حافظه: ۲۵۶ مگابایت

بدخواه، بدِ جامعه‌ی هنری را هم میخواهد. او تدارک ساخت فیلمی را داده و از $n$ بازیگر مطرح سینما دعوت کرده که در فیلم او بازی کنند. آن‌ها با دیدن فیلمنامه قبول کردند، غافل از نقشه‌هایی که بدخواه برایشان دارد...

بدخواه در همان روز اول کار، به سراغ فیلمبرداری صحنه‌ی پایانی میرود - صحنه‌ی دوئل. در این صحنه، این $n$ بازیگر حضور دارند و هریک کسی را در ذهن خود هدف میگیرد، بطوری که هرکس توسط دقیقاً یک نفر هدف‌گرفته شود. بازیگر $i$ ـم، بازیگر $p_i$ ـم را هدف قرار می‌دهد. در یک لحظه همه‌ی بازیگرها اقدام به شلیک میکنند اما سرعت عکس‌العمل آن‌ها برابر نیست و بازیگر $i$ ـم، $t_i$ میلی ثانیه طول میکشد تا ماشه‌ را بچکاند و طعم مرگ‌ را به بازیگر $p_i$ ـم بچشاند. بدلیل حرفه‌ای بودن این بازیگرها، هریک دقیقاً به اندازه‌ی مقدار تعیین شده ( $t_i$ میلی ثانیه) صبر کرده و سپس بسرعت، هفت‌تیر را بالا آورده و به هدفش ( $p_i$ ـمین بازیگر) شلیک میکند. این اعمال در زمان اندک انجام میشود.(می‌توان فرض کرد اگر شلیک انجام شود، فرد $p_i$ در لحظه‌ی $t_i$ می‌میرد.)

اما بدخواهِ نابکار، در هفت‌تیر این افتخارات ملی، تیر‌های واقعی گمارده و با هر شلیک، یک جوان هنرمند می‌میرد. اگر بازیگر $i$ ـم قبل از زمان $t_i$ مرده باشد، در لحظه‌ی $t_i$ شلیکی از طرف این بازیگر صورت نمی‌گیرد.

حال بدخواه سناریو‌ را به شما می‌دهد (مقدار $t_i$ ها و $p_i$ ها) و از شما می‌پرسد که با اجرای این سناریو، در نهایت چند بازیگر زنده می‌مانند. سپس به امید کشته‌های بیشتر، $q$ بار این سناریو را عوض میکند؛ هربار یکی از $t_i$ ها را تغییر می‌دهد و پس از هر تغییر نیز از شما می‌پرسد که حال چطور؟! و شما باید تعداد بازیگرهای زنده پس از اجرای این سناریو را به او بگویید.

دقت کنید که تغییرات انجام شده باقی می‌مانند؛ بعنوان مثال دومین تغییر روی سناریو ای صورت می‌گیرد که پیش از آن، اولین تغییر روی آن اعمال شده است.

ورودی🔗

سطر اول ورودی شامل یک عدد $n$ است که نمایانگر تعداد بازیگرها در سناریوی بدخواه است.

در سطر دوم ورودی، $n$ عدد متفاوت آمده است. $i$ ـمین عدد $p_i$ است که نمایانگر هدف بازیگر $i$ ـم در سناریوی اولیه است.

در سطر سوم ورودی، $n$ عدد آمده است. $i$ ـمین عدد $t_i$ است که نمایانگر زمان عکس‌العمل بازیگر $i$ ـم در سناریوی اولیه است.

در سطر چهارم ورودی، یک عدد $q$ آمده است که نمایانگر تعداد تغییرهای سناریو است. سپس در $i$ ـمین سطر از $q$ سطر بعدی، دو عدد $b_i$ و $y_i$ آمده است که یعنی در تغییر $i$ ـم، زمان عکس‌العمل بازیگر $b_i$ ـم در سناریو به $y_i$ تغییر میکند.

تضمین می‌شود که همه‌ی اعداد $t_1, t_2, t_3, ..., t_n, y_1, y_2, y_3, ..., y_q$ متفاوت هستند.

$p_i \neq i$ $2 \le n \le 200\ 000$ $0 \le q \le 200\ 000$ $1 \le p_i, b_i \le n$ $1 \le y_i, t_i \le 1\ 000\ 000\ 000$

خروجی🔗

خروجی باید شامل $q + 1$ سطر باشد که هرکدام شامل یک عدد هستند. عدد در سطر اول باید برابر تعداد بازیگرهای زنده درصورت اجرای سناریوی اولیه است. عدد در $i + 1$ ـمین سطر باید برابر تعداد بازیگرهای زنده باشد، در صورتی که $i$ تغییر اول روی سناریوی اولیه انجام شود و سناریو را اجرا کنند.

مثال🔗

ورودی نمونه🔗

خروجی نمونه🔗