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

شیرین عسل فهمید که یار نامه‌اش را کامل نخوانده است و تصمیم گرفت برود سراغ یار!!

یار که خیلی ترسیده است می‌خواهد هر چه زودتر از خانه اش بیرون برود.

خانه‌ی یار $n$ اتاق دارد که هر اتاق یک در خروجی و یک عدد از بین $0$ تا $k - 1$ دارد که درِ خروجی هر اتاق به جز اتاق $n$ام به اتاق بعدی باز می‌شود و در اتاق $n$ام به بیرون خانه باز می‌شود و در ثانیه‌ی t در خروجی اتاق‌هایی باز است که عدد آن ها برابر باقی‌مانده‌ی تقسیم $t$ بر $k$ است.

به ازای هر اتاق به یار بگویید که اگر در ثانیه‌ی $0$ در آن اتاق باشد و به بهترین شکل عمل کند در چه ثانیه‌ای می‌تواند از خانه خارج شود (یار در یک ثانیه هر مسافتی را می‌تواند طی کند).

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $k$ با فاصله آمده‌اند که در متن سوال توضیح داده شده اند و در سطر بعد $n$ عدد ($a_1 ... a_n$) که با فاصله از هم جدا شده اند آمده که $a_i$ نمایانگر عدد اتاق $i$ام است.

$1 \le n , k \le 100\ 000$ $0 \le a_i \le k - 1$

خروجی🔗

خروجی باید شامل $n$ خط باشد که در خط $i$ام جواب به ازای اتاق $i$ام را چاپ کنید.

مثال🔗

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

6 3
2 1 1 0 1 0 

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

9
6
6
3
3
0

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

یار در حین فرار از دست شیرین عسل به یک درِ بسته برخورد!!

برای باز کردن این در یار باید یک معما را حل کند؛ که از تعدادی چرخدنده تشکیل شده است ولی انقدر از فرار کردن خسته شده است که نمی‌تواند رفتار چرخ دنده‌ها را تحلیل کند به همین خاطر از شما می‌خواهد به چند سوال در مورد این چرخدنده‌ها پاسخ دهید.

توجه کنید که تعدادی چرخدنده در صفحه همیشه چند ویژگی دارند:

1. اگر دو چرخدنده با هم در تماس باشند یا هر دو ثابت اند یا هر دو می‌چرخند.
2. اگر دو چرخدنده با هم تماس داشته باشند و در حال چرخش باشند حتمن جهت چرخش آن‌ها خلاف یک‌دیگر است (یکی ساعت‌گرد و دیگری پادساعت‌گرد)

سوال‌هایی که شما باید به آن‌ها جواب بدهید به این صورت هستند: اگر چرخدنده‌ی $a$ ساعت‌گرد بچرخد برای چرخدنده‌ی $b$ چه اتفاقی می‌افتد؟؟

و یکی از جواب‌های زیر را باید به هر سوال بدهید:

1. هیچ‌گاه چرخدنده‌ی $a$ ساعت‌گرد نمی‌چرخد (impossible).
2. الزامن چرخدنده‌ی $b$ ساعت‌گرد می‌چرخد (cw).
3. الزامن چرخدنده‌ی $b$ پادساعت‌گرد می‌چرخد (ccw).
4. چرخدنده‌ی $a$ می‌چرخد اما برای چرخدنده‌ی $b$ هر اتفاقی ممکن است بی‌افتد (independent).

ورودی🔗

در سطر اول ورودی سه عدد طبیعی $n$ و $m$ و $q$ با فاصله آمده اند که به ترتیب نمایانگر تعداد چرخدنده‌ها، تعداد جفت چرخدنده‌هایی که با یک‌دیگر در تماس‌اند و تعداد سوال‌هایی که باید به آن‌ها جواب بدهید هستند. در $m$ سطر بعدی در هر سطر دو عدد طبیعی $v$ و $u$ با فاصله آمده است که نشان دهنده‌ی در تماس بودن چرخدنده‌های $v$ و $u$ است و در $q$ سطر بعدی در هر سطر دو عدد $a$ و $b$ آمده است که توضیح یک سوال است. هر جفت چرخدنده حداکثر یک بار در توضیح تماس‌ها می‌آید و تضمین می‌شود می‌توان چرخدنده‌ها را در صفحه قرار داد.

$3 \le n \le 100\ 000$ $1 \le q \le 100\ 000$ $0 \le m \le 3n - 6$ $1 \le a, b, v, u \le n$

خروجی🔗

جواب هر سوال را همانطور که در صورت سوال آمده است در یک سطر چاپ کنید.

مثال🔗

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

5 4 3
1 2
3 4
4 5
5 3
1 2
1 3
3 1

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

ccw
independent
impossible

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

شیرین عسل وقتی به خانه‌ی یار رسید بر خلاف تصور همگان (به ویژه یار) به یاداشت گذاشتن بسنده کرد!!

او متوجه شد که اگر برای یار یادداشت بگذارد توسط یک ماشین برخی از کاراکترهای یاداشت پاک می‌شوند و سپس یاداشت به دست یار می‌رسد. شیرین عسل می‌خواهد کوتاه‌ترین یادداشتی را بنویسد که پس از حذفیات یادداشت مورد نظر شیرین عسل باقی‌بماند.

این ماشین به این صورت کار می‌کند که با وضعیت $1$ شروع می‌کند و به ترتیب حروف نامه را بررسی می‌کند و با توجه به وضعیت ماشین و قوانینی که یار برای ماشین تعریف کرده است در بررسی هر یک از حروف یکی از کارهای زیر را انجام می‌دهد:

1. اگر ماشین در وضعیت $v$ باشد و حرفی که ماشین در حال بررسی آن است برابر $c$ باشد و قانونی مانند v u c وجود داشته باشد آن حرف پاک می‌شود و وضعیت ماشین به $u$ تغییر می‌کند ($v$ و $u$ اعداد طبیعی و نمایانگر شماره وضعیت هستند و $c$ یک حرف کوچک انگلیسی است).
2. اگر هیچ قانونی مانند v u c وجود نداشته باشد وضعیت ماشین تغییر نمیکند و آن حرف پاک نمی‌شود و دستگاه به بررسی حرف بعدی می‌پردازد.

طول کوچک‌ترین یاداشتی که شیرین عسل می‌تواند بنویسد را به او بگویید.

شکل برای نمونه ۱

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$‌ و $m$ آمده است که به ترتیب نمایانگر تعداد وضعیت‌های ماشین و تعداد قوانین است. در خط بعدی رشته‌ی $s$ شامل حروف کوچک انگلیسی آمده است که نمایانگر متن یادداشت مورد نظر شیرین عسل است. سپس در $m$ ‌خط بعدی در هر خط توضیح یکی از قوانین به صورت v u c آمده است. $1 \le n \le 1\ 000$ $1 \le m \le 26\ 000$ $1 \le |s| \le 1\ 000$ $1 \le v , u \le n$ تضمین می‌شود هیچ دو قانونی با $v$ و $c$ یکسان وجود ندارند.

خروجی🔗

در تنها سطر خروجی جواب مسئله را چاپ کنید و اگر هیچ یادداشتی نمی‌تواند به شیرین عسل کمک کند $-1$ را چاپ کنید.

مثال🔗

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

2 2
baba
1 2 a
2 1 b

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

7

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

3 3
yar
1 2 a
2 3 a
3 1 a

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

-1

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۲۸ مگابایت

شیرین عسل به کل دست از سر یار برداشته و قصد پرداختن به کار علمی دارد.

او در آزمایشگاه خود $n$ موش آزمایشگاهی دارد که هر کدام مقداری سلامتی دارند و با شماره‌های $1$ تا $n$ شماره گذاری شده اند. در ابتدا، در پایان هر روز که ‌می‌گذرد $1$ واحد از سلامتی هر موش کم می‌شود.

شیرین عسل در ابتدایِ هر روز یکی از کارهای زیر را انجام می‌دهد:

1. تعداد موش‌های زنده از موشِ $l$ام تا $r$ام را می‌پرسد.
2. به موش $i$ام یک ویروس با قدرت $val$ می‌دهد که باعث می‌شود از آن روز به بعد در پایان هر روز $val$ واحد بیشتر از قبل از سلامتی موش کم شود (یعنی اگر تا قبل از ویروس دادن هر روز $x$ واحد از سلامتی‌اش کم می‌شد از این به بعد هر روز $x + val$ واحد کم می‌شود).

منطقن هر موشی که سلامتی‌اش به صفر برسد یا منفی شود دیگر زنده نیست.

شما باید جواب سوال‌های شیرین عسل را بدهید.

ورودی🔗

در سطر اول ورودی دو عدد طبیعی $n$ و $q$ با فاصله آمده‌اند که به ترتیب نمایانگر تعداد موش‌ها و تعداد روز‌هایی که شیرین عسل در آزمایشگاه مشغول است هستند. در سطر دوم $n$ عدد ($a_1...a_n$) با فاصله آمده‌اند که $a_i$ سلامتی موش $i$ام است. در $q$ سطر بعدی فعالیت‌های شیرین عسل در هر روز به ترتیب و به صورت ? l r یا + i val آمده است (هر روز در یک سطر).

$1 \le n, q \le 400\ 000$ $1 \le a_i \le 1\ 000\ 000\ 000$ $1 \le l \le r \le n$ $1 \le i \le n$ $1 \le val \le 100\ 000$

خروجی🔗

به ترتیب به ازای هر پرسش جواب را در یک خط چاپ کنید.

مثال🔗

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

5 7
3 1 8 4 2
? 1 5
? 1 5
+ 4 1
? 2 5
+ 3 2
? 2 5
? 2 5

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

5
4
1
1
0

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

سید که دید شیرین عسل دنبال علم آموزی رفته است او را با علوم خفن آشنا کرد!!

سید به شیرین عسل یک درخت $n$ راسی داد و گفت:

اگر این درخت را از یک راس غیر برگ ریشه دار کنیم $f(v)$ برای هر راس به اینصورت تعریف می‌شود که اگر $v$ برگ باشد $f(v) = 1$ خواهد بود و در غیر این صورت اگر $grandChildren(v)$ مجموعه‌ی رئوس زیر درخت راس $v$ به جز خودش باشد: $f(v) = \sum_{A\ \subseteq\ grandCildren(v)}^{A\ \neq\ \varnothing} (\prod_{u\ \in A}^{} f(u))$ $\prod_{}^{}$ مثل $\sum_{}^{}$ عمل می‌کند فقط به جای حاصل جمع، حاصل ضرب است.

واضح است که با تغییر ریشه مقدار $f$ برای رئوس مختلف ممکن است تغییر کند. فرض کنید درخت را از راسی ریشه دار کرده‌ایم که مقدار $f$ برای ریشه حداقل شده است و $f$ برای ریشه برابر $x$ است. شیرین عسل که با علوم خفن حال کرده است می‌خواهد بداند باقی مانده‌ی تقسیم $x$ بر عدد $1\ 000\ 000\ 007$ چند است (توجه کنید که بنابر تعریفِ $f$، ریشه نباید برگ باشد).

ورودی🔗

در سطر اول ورودی عدد طبیعی $n$، تعداد رئوس درخت آمده است و در $n - 1$ خط بعدی در هر خط توضیح یک یال از درخت به صورت v u آمده است که نشان دهنده‌ی وجود یال بین رئوس $v$ و $u$ است. تضمین می‌شود گراف ورودی درخت است.

$3 \le n \le 100\ 000$ $1 \le v, u \le n$

خروجی🔗

جواب مسئله را در یک خط چاپ کنید.

مثال🔗

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

7
1 2
2 3
2 4
2 5
3 6
3 7

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

127

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

3
1 2
2 3

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

3