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

عرفان و متین شطرنج بازی می‌کنند. مهره‌های رخ عرفان در $(x_1, y_1)$ و $(x_2, y_2)$ و متین در $(x_3, y_3)$ و $(x_4, y_4)$ قــرار دارد (۲ مهره در یک خانه قرار ندارند). عرفان به مهره‌ی رخش «زیبا» می‌گوید در صورتی که حداقل یکی از مهـره‌های رخ متین را تهدید کند (از نظر عرفان در صـورتی کـه دو مهره رخ هـم سـطر یـا هـم سـتون بـاشند یکدیگر را تهدید می‌کنند). عرفان اگر دقیقاً یکی از ۲ رخش «زیبا» باشد خوش حال می‌شود. متین از شما می‌خواهد که بگویید عرفان خوش حال است یا خیر.

ورودی🔗

در سطر $i$ام $(1 \leq i \leq 4)$ به ترتیب $x_i$ و $y_i$ می‌آیند.

$1 \leq x_i, y_i \leq 8$

خروجی🔗

اگر عرفان خوش حال می شود چاپ کنید happy در غیر این صورت چاپ کنید unhappy.

مثال‌ها🔗

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

1 1
2 2
3 3
4 4

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

unhappy

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

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

1 1
1 2
1 3
8 2

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

unhappy

رخ اول عرفان که در $(1, 1)$ قرار دارد رخ اول متين را که در $(3, 1)$ قرار دارد تهدید می‌کند پس رخ اول عرفان زيبا است. رخ دوم عرفان هم که در $(2, 1)$ قرار دارد هر ۲ رخ متین را تهدید می‌کند، پس این رخ هم زيبا است. از آنجایی که هر ۲ رخ عرفان زیبا هست پس عرفان خوش‌حال نیست.

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

2 1
4 3
2 7
8 6

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

happy

رخ اول عرفان که در $(1, 2)$ قرار دارد رخ اول متین را که در $(7, 2)$ قرار دارد تهدید می‌کند پس این رخ زيبا است. رخ دوم عرفان که در $(3, 4)$ قرار دارد هیج کدام از رخ های متین را تهدید نمی‌کند پس زیبا نیست. از آنجایی که دقيقاً یکی از ۲ رخ عرفان زيبا است پس عرفان خوش‌حال است.

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

استاد و $k$ شاگردش بـه مـغازه شکلات فـروشی سـر کوچه که $n$ جـعبه شکلات دارد می‌رونـد. جعبه شـکلات $i$ام $a_i$ شکلات دارد و $c_i$ تومان قیمت دارد. استاد و شاگردانش در صورتی حین خوردن یک جعبه شکلات دعوایشان نمی‌شود که ۲ شرط زیر برقرار باشد:

1. شاگرد‌ها همه به تعداد برابر شکلات بخورند و استاد دقيقاً ۱ شکلات از شاگرد‌ها بيشتر.
2. همه حداقل ۱ شکلات بخورند.

دقت کنید که شکلات‌ها بین افراد افراز می‌شود (یعنی همه‌ی شکلات‌ها پخش می‌شود و یک شکلات را ۲ نــفر نمی‌خورند). اسـتاد $v$ تومان پـول دارد و بـا پـولـش می‌خواهد بیشـتریـن تعداد جعبه شکلات را بخرد به طوری که حین خـوردن هیچ کدام از جعبه شکلات‌ها بـینشان دعوا نشود (دقت کنید، ابتدا یک جعبه شکلات را بین خود تقسیم می‌کنند و می‌خوردند و سپس جعبه بعدی را باز می‌کنند). حال استاد از شما می‌خواهد تا بگویید حداکثر چند جعبه شکلات می‌تواند بخرد.

ورودی🔗

در سطر اول به ترتيب سه عدد $k$، $v$ و $n$ و در سطر بعدی $n$ عدد می‌آید که $i$امين آن‌ها $a_i$ است و درسطر بعدی $n$ عدد می‌آید که $i$امین آن‌ها $c_i$ است.

$1 \leq n, k \leq 100000$ $1 \leq c_i, a_i, v \leq 10^9$

خروجی🔗

تعداد حداکثر جعبه شکلاتی که می‌توانند بخرند و با خوردنش بینشان دعوت نشود.

مثال‌🔗

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

3 10 5
5 9 10 4 14
1 10 2 1 3

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

1

جعبه‌های اول و دوم را می‌توان بخرد به طوری کـه حین خـوردن شکلات‌هایش بـینشان دعـوا نشود و با پولی که دارد از میان این ۲ حداکثر یکی را می‌تواند بخرد.

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

عرفان و دوستانش که مجموعاً $3n$ نفر می‌شوند به سینما رفتند و روی $3n$ صندلی متوالی در یک رديف نشستند. آن‌ها با خود $n + 1$ بسته پاپ كورن به سینما بردند. قرار شد $n + 1$ پاپ کورن بین افراد تقسم شود به نحوی که به هر نفر حداکثر یک بسته پاپ کورن برسد. در صورتی یک نفر از فیلم لذت می‌برد که یا خود یا یکی از ۲ نفر بغل دستی‌اش (۲ نفر کناری هر کدام ۱ بغل دستی دارند) پاپ کورن داشته باشد. حال برای عرفان سوال شده است که به چند طريق می‌توان پاپ کورن‌ها را بین افراد تقسیم کرد که همه از فیلم لذت ببرند.

ورودی🔗

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

$1 \leq T \leq 100 \, 000$

$1 \leq n \leq 10^9$

خروجی🔗

بـه ازای هـر تسـت تعداد حالات افراز $n + 1$ پـاپ کورن بین $3n$ نفر به طوری که همه از فیلم لذت ببرند را به پیمانه‌ی $10^9 + 7$ چاپ کنید.

مثال🔗

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

3
1
2
3

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

3
10
22

حالات مطلوب برای $n = 1$ (عدد $1$ پاپ کورن دارد $0$ ندارد) :

$101 \mid 110 \mid 011$

حالات مطلوب برای $n = 2$ (عدد $1$ پاپ کورن دارد $0$ ندارد) :

$110010 \mid 101010 \mid 011010 \mid 100110 \mid 010110$

$101001 \mid 011001 \mid 100101 \mid 010101 \mid 010011$

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

در بازی OSTADD که یک بازی جنگی است $n$ نوع تفنگ وجود دارد که تفنگ $i$ام $t_i$ تیر دارد که هر تیر $p_i$ قدرت دارد و برای خریدش $c_i$ هزینه لازم است. دشمن $m$ گروه دارد که گروه $i$ام $a_i$ نفر هستند و هر کدام $b_i$ جان دارد (یعنی برای این که بمیرد باید تیری به قدرت بیشتر مساوی $b_i$ به او شلیک کرد). ما می‌خواهیم همه افراد دشمن را با زدن دقيقاً یک تیر به هر یک از آن‌ها بکشیم. حداقل هزینه برای خرید تفنگ برای کشتن تمام افراد دشمن چه قدر است.

ورودی🔗

در سطر اول عدد $n$ می‌آید و در $n$ سطر بعدی در هر سطر به ترتیب $t_i$، $p_i$ و $c_i$ که اطلاعات تفنگ $i$ام است می‌آید و در سطر بعد عدد $m$ و در $m$ سطر بعدی در هر سطر به تریب $a_i$ و $b_i$ می‌آید که اطلاعات گروه $i$ام دشمن است. $1 \leq n, m \leq 500$ $1 \leq a_i, t_i \leq 100$ $1 \leq p_i, b_i, c_i \leq 1000000000$

خروجی🔗

حداقل هزینه برای خرید تفنگ برای کشتن تمام افراد دشمن چه قدر است. اگر این کار ممکن نیست -1 چاپ کنید.

مثال‌ها🔗

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

2
2 3 5
1 4 10
1
3 2

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

15

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

3
2 3 5
2 4 10
4 4 20
2
1 4
3 3

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

15

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

1
5 3 10
1
3 5

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

-1

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

سینا به عرفان یک آرایه از $n$ عدد هديه داده است. ایلیا از عرفان می‌خواهد $Q$ عمليات روی آرایه انجام دهد. هر عملیات به یکی از ۴ حالت زیر است:

1. $0 \, l \, r : \sum a_i \quad (l \leq i \leq r)$
2. $1 \, l \, r \, v : a_i := a_i \oplus v \quad (l \leq i \leq r)$
3. $2 \, l \, r \, v : a_i := a_i \text{ and } v \quad (l \leq i \leq r)$
4. $3 \, l \, r \, v : a_i := a_i \text{ or } v \quad (l \leq i \leq r)$

عرفان باید عملیات های گفته شده را روی اعضای ارایه اعمال کند و در ازای هر نوع عملیات از نوع $0$ جمع اعداد درون بازه خواسته شده را به ایلیا بگوید. اما از انجایی که عرفان خسته شده است، از شما می خواهد پاسخ سوالات ایلیا را بدهید.

ورودی🔗

در سطر اول به ترتیب عدد $n$ که طول آرایه است و در سطر بعد $n$ عدد که $i$امین شان $a_i$ است می‌آید. در سطر بعد $Q$ می‌آید و در $Q$ سطر بعدی در هر سطر یک عملیات از ۴ عمليات ذکر شده می‌آید. $1 \leq n, Q \leq 100\,000$ $1 \leq l \leq r \leq n$ $1 \leq a_i , v \leq 1000\,000$

خروجی🔗

در ازای هر عملیات از نوع $0$ جمع اعداد درون بازه خواسته شده را خروجی دهید.

مثال🔗

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

4
1 2 4 8
5
1 2 3 8
3 1 1 8
0 1 3
2 1 4 8
0 2 4

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

31
24

نتیجه اعمال هر عملیات:

1. $a : [1, 10, 12, 8]$
2. $a : [9, 10, 12, 8]$
3. $print : 9 + 10 + 12 = 31$
4. $a : [8, 8, 8, 8]$
5. $print : 8 + 8 + 8 = 24$

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

اهورا به عرفان $n$ رشته هدیه داده است که $i$امین آن‌ها $s_i$ است. آرمین از عرفان $q$ سوال می‌پرسد. در پرسش $i$ام تعداد جفت $y$ و $x$هایی را می‌خواهد که شرایط زیر را داشته باشند:

1. $1 \leq x \lt y \leq p_i$
2. $l_i \leq lcp(s_x, s_y) \leq r_i$

فرض کنید ۲ رشته $a$ و $b$ داریم $lcp(a, b)$ برابر است با طول بلند ترین پیشوند مشترک آن‌ها.

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

ورودی🔗

در سطر اول عدد $n$ می‌آید و در $n$ سطر بعدی $s_i$ (رشته‌ها متشکل از حروف کوچک انگلیسی هستند) می‌آید. در سطر بعد $q$ می‌آید و در $q$ سطر بعد به ترتیب $p_i$، $l_i$ و $r_i$ می‌آید. $1 \leq n \leq 500\,000$ $1 \leq q \leq 1000\,000$ $\sum |s_i| \leq 500\,000$ $2 \leq p_i \leq n$ $0 \leq l_i \leq r_i \leq 1000\,000$

خروجی🔗

در ازای پرسش $i$ تعداد زوج‌های نامرتب $(x, y)$ که در شرایط گفته شده صدق می‌کنند را خروجی دهید.

مثال🔗

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

3
abb
acd
abd
3
3 1 2
3 0 1
2 2 3

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

3
2
0

• $lcp(s_1, s_2) = 1$
• $lcp(s_2, s_3) = 1$
• $lcp(s_1, s_3) = 2$

پرسش اول. در ۳ رشته‌ی اول هر ۳ جفت رشته‌ای که داریم $lcp$ آن‌ها بین ۱ و ۲ است.

پرسش دوم‌. در ۳ رشته‌ی اول $0 \leq lcp(s_1, s_2) = lcp(s_2, s_3) \leq 1$

پرسش سوم. در ۲ رشته‌ی اول $lcp(s_1, s_2) \lt 2$