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

شیرین عسل می‌خواهد به یار نامه بنویسد!!

در زبانی که شیرین عسل با آن نامه می‌نویسد همه‌ی حروف یک کلمه با هم برابراند و هیچ وقت دو کلمه که حروف یکسان دارند درکنار هم نمی‌آیند. به همین دلیل نیازی به استفاده از فاصله بین کلمات ندارند. مثلن $aabbbahh$ از کلمات $aa, bbb, a, hh$ تشکیل شده است.

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

منطقن شیرین عسل دوست ندارد یار از نامه‌ بدش بیاید پس از یک آدم کار بلد (شما رو میگه!!) می‌خواهد که نامه را چک کند.

ورودی🔗

در سطر اول ورودی رشته‌ی $s$ شامل حروف کوچک انگلیسی آمده است که نمایانگر متن نامه است.

$1 \le |s| \le 1000$

خروجی🔗

در تنها سطر خروجی اگر یار از نامه بدش می‌آید bad در غیر این صورت khoob را چاپ کنید.

مثال🔗

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

aabbcccc

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

khoob

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

aaboooo

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

bad

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

یار عادت دارد اول هر نامه‌ای که به دستش می‌رسد را پاک کند(نه لزومن نامه‌ی شیرین عسل)!! و برای این کار یک ماشین ساخته است.

این ماشین به این صورت کار می‌کند که با وضعیت $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
ababbarbari
1 2 a
2 1 b

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

barbari

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

شکل سمت چپ

3 4
abcadc
1 2 a
2 3 b
2 3 d
3 1 c

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

-1

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

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

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

خانه‌ی یار $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

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

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

او در آزمایشگاه خود $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