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

از زمان‌های قدیم در ایران، سه سفر زیارتی هست که باعث می‌شود لقبی پشت اسم شما اضافه شود. سفر حج لقب «حاجی»، سفر کربلا لقب «کربلایی» و سفر مشهد لقب «مشتی» را به دنبال دارد. همچنین اگر یک نفر چند سفر را رفته باشد، اولویت لقب او به ترتیب با «حاجی»، «کربلایی» و «مشتی» است. حال به شما سفرهایی که یک نفر رفته است را به صورت یک رشته ۳ تایی از کاراکترهای Y و N می‌دهیم و از شما می‌خواهیم لقب درستی که باید نسبت دهیم را چاپ کنید. (اگر هیچ سفری نرفته بود به او «آقا» می‌گوییم.)

ورودی🔗

در تنها سطر ورودی، یک رشته به طول ۳ از حروف Y (بله) و N (خیر) داده می‌شود که به‌ترتیب نشان‌دهنده‌ی تجربه‌ی سفر به «حج»، «کربلا» و «مشهد» است.

خروجی🔗

در صورتی که لقب «حاجی» است رشته‌ی Haji، «کربلایی» است رشته‌ی Karbalaee، «مشتی» است رشته‌ی Mashti و درصورتی که هیج کدام از این لقب‌ها را ندارد، Agha چاپ کنید.

مثال🔗

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

YNY

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

Haji

این شخص به سفر مکه رفته و به سفر کربلا نرفته و به سفر مشهد رفته. پس می‌تواند لقب‌های «حاجی» و «مشتی» را داشته باشد ولی چون لقب «حاجی» به «مشتی» اولویت دارد، خروجی حاجی می‌شود.

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

NNN

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

Agha

این شخص به هیچکدام از این سه سفر نرفته، پس لقب او «آقا» می‌شود.

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

NNY

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

Mashti

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

NYY

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

Karbalaee

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

دکارت که از مختصات ابداعیش خوشش آمده تصمیم به طرح جدول دکارتی با استفاده از _ و | می‌گیرد. جدول دکارتی $n×m$ جدولی است که $n$ سطر و $m$ ستون دارد. حال از شما می‌خواهیم که جدول دکارتی را با چوب کبریت مشابه نمونه‌ها بسازید!

ورودی🔗

در تنها سطر ورودی به ترتیب دو عدد صحیح مثبت نشانگر تعداد سطرها و ستون‌ها جدول می‌آید. تضمین می‌شود که تعداد سطرها و ستون‌ها حداکثر مقدارشان ۱۰ است.

خروجی🔗

با استفاده از فاصله و چوب‌کبریت افقی _ و چوب‌کبریت عمودی | جدول دکارت را مشابه نمونه بسازید. (چاپ فاصله در انتهای خطوط مهم نیست.)

مثال🔗

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

1 1

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

 _
| |
 _

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

3 4

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

 _ _ _ _
| | | | |
 _ _ _ _
| | | | |
 _ _ _ _
| | | | |
 _ _ _ _

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

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

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت $t$ آمده است که تعداد سناریوها را نشان می‌دهد. $1 \leq t \leq 100 \, 000$

در سطر اول هر سناریو عدد صحیح و مثبت $n$ آمده است که تعداد زوج‌ها را نشان می‌دهد. $1 \leq n \leq 100 \, 000$

در سطر دوم هر سناریو، $2n$ رشته آمده که رشته‌ی $i$ام وضعیت نفر $i$ام در صف را نشان می‌دهد. هر وضعیت به فرمت یک کاراکتر و یک عدد است که کاراکتر اول W (زن) یا M (مرد) بوده و عدد بعد از آن شماره‌ی زوج را نشان می‌دهد. زوج‌ها با $1$ تا $n$ شماره گذاری می‌شوند.

تضمین می‌شود در هر سناریو ورودی شامل همه‌ی $2n$ نفر باشد. همچنین تضمین می‌شود مجموع $n$ها برای همه‌ی $t$ سناریو حداکثر ۱۰۰،۰۰۰ باشد.

زیرمسئله‌ها🔗

خروجی🔗

در $t$ سطر در صورتی که می‌توان با یک جابه‌جایی زوج‌ها کنار هم گذاشت، YES و در غیر این‌صورت NO چاپ کنید.

مثال🔗

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

3
1
M1 W1
4
W1 M1 W4 M2 W3 M3 M4 W2
3
W1 W2 W3 M1 M2 M3

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

YES
YES
NO

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

استاد امروز شئ شبیه به کیک از دوستش دریافت کرده. شئ شبیه به کیک شامل $n$ ستون است که ستون $i$ام آن (با شماره‌گذاری از چپ به راست) $a_{i}$ لایه دارد. استاد برای این که بفهمد آیا شئ شبیه به کیک واقعا کیک است یا نه تصمیم گرفته فرایند زیر را انجام دهد:

او در هر مرحله می‌تواند $k$ ستون متوالی از شئ که در هر کدام از این ستون‌ها حداقل یک لایه باقی مانده را انتخاب کند و از هرکدام از این ستون‌ها یک لایه حذف کند. اگر پس از تعدادی مرحله تمام ستون‌ها خالی شدند (تمام لایه‌های هر ستون حذف شدند) استاد به این نتیجه می‌رسد که شئ شبیه به کیک واقعاً کیک بوده. در غیر این صورت متوجه می‌شود که شئ واقعاً کیک نبوده (و در نتیجه در کمال تعجب نه واقعی بوده و نه کیک).

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

ورودی🔗

ورودی شامل $t$ سناریو است. اطلاعات سناریوها در خطوط متمایز و متوالی به شرح زیر برای هر سناریو می‌آید. خط اول سناریو $s$ شامل دو عدد $n_s$ و $k_s$ می‌شود.

خط بعدی شامل $n_s$ عدد $a_{1}, a_{2}, ... a_{n}$ می‌شود که در آن، $a_{i}$ نشان دهنده‌ی تعداد لایه‌های ستون $i$ام از شئ است.

$1 \leq t \leq 10^4$

$1 \leq k_{s} \leq n_{s} \leq 10^6$

$0 \leq a_{i} \leq 10^9$

$\sum_{s=1}^{t} n_{s} \leq 10^6$

خروجی🔗

در خروجی در صورتی که شیئ واقعا کیک است عبارت Cake و در غیر این صورت عبارت Fake را چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

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

3
7 3
1 2 3 4 3 2 1
7 4
1 2 3 4 3 2 1
6 2
3 4 1 0 1 2

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

Fake
Cake
Fake

توضیحات نمونه:

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

1. از ستون سوم تا ششم یک لایه کم کند تا شئ به صورت 1 2 2 3 2 1 1 دراید.
2. از ستون دوم تا پنجم یک لایه کم کند تا شئ به صورت 1 1 1 2 1 1 1 دراید.
3. از ستون چهارم تا هفتم یک لایه کم کند تا شئ به صورت 1 1 1 1 0 0 0 دراید.
4. از ستون اول تا چهارم یک لایه کم کند تا شئ به صورت 0 0 0 0 0 0 0 دراید.

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

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

استاد که اخیرا زمان زیادی را تنهایی سپری می‌کند تصمیم گرفته تنهایی مار و پله بازی کند.

بازی از $n$ خانه با شماره‌های $1$ تا $n$ تشکیل شده. همچنین در صفحه‌ی بازی $l$ پله و $s$ مار قرار دارند. پله‌ی $i$ام بین خانه‌های $a_{i}$ و $b_{i}$ $(a_{i} < b_{i})$ قرار دارد و اگر استاد در لحظه‌ای از بازی در خانه‌ی $a_{i}$ قرار بگیرد باید با استفاده از پله به خانه‌ی $b_{i}$ برود. مار $i$ام نیز بین خانه‌های $c_{i}$ و $d_{i}$ $(c_{i} > d_{i})$ قرار دارد و اگر استاد در لحظه‌ای از بازی در خانه‌ی $c_{i}$ قرار بگیرد توسط مار نیش زده می‌شود و به خانه‌ی $d_{i}$ می‌رود.

او در هر لحظه از بازی می‌تواند یک عدد مثل $k$ بین $1$ تا $6$ انتخاب کند و $k$ خانه از خانه‌ی فعلیَش جلوتر برود (به شرطی که مقصد حدکثر $n$ باشد). بازی از خانه ۱ شروع شده و در خانه $n$ خاتمه می‌یابد.

از آن‌جایی که تنهایی بازی کردن چندان مفرح نیست،‌ استاد تصمیم گرفته به جای بازی کردن کمینه‌ی تعداد مراحلی که نیاز دارد تا از خانه‌ی ۱ به خانه‌ی $n$ برسد را محاسبه کند. به او در این کار کمک کنید.

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

ورودی🔗

ورودی شامل $t$ سناریو است. اطلاعات سناریوها در خطوط متمایز و متوالی به شرح زیر برای هر سناریو می‌آید. خط اول سناریو شماره $u$ شامل سه عدد $n_u$، $l_u$ و $s_u$ می‌شود که به ترتیب تعداد خانه‌های بازی،‌ پله‌ها و مارها را نشان می‌دهند.

خط $i$ام خط از $l_u$ خط بعدی شامل دو عدد $a_{i}$ و $b_{i}$ می‌شود که به ترتیب نشان دهنده‌ی خانه‌های ابتدایی و انتهایی $i$امین پله‌اند.

نهایتا $i$امین خط از $s_u$ خط بعدی شامل دو عدد $c_{i}$ و $d_{i}$ می‌شود که به ترتیب نشان دهنده‌ی خانه‌های سر و دم $i$امین ماراند. $1 \le t \le 10\,000$ $2 \le n_u \le 200\, 000$ $\sum_{u=1}^t n_u \le 200 \, 000$ $0 \le l_u + s_u \le n_u-2$ $2 \le a_i < b_i \le n_u$ $1 \le d_i < c_i < n_u$ $a_i \ne a_j, a_i \ne c_j, c_i \ne c_j \quad (i \ne j)$

خروجی🔗

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

مثال🔗

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

4
100 0 0
100 2 2
7 70
8 80
82 54
99 1
30 2 0
8 23
7 18
100 1 1
5 99
99 4

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

17
6
3
17

توضیحات نمونه:

در سناریوی اول یکی از بهترین روش‌هایی که استاد می‌تواند پیش بگیرد این است که در هر مرحله بیشترین میزانی که می‌تواند به جلو برود. با این روش استاد پس از $17$ مرحله به خانه‌ی $100$ می‌رسد.

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

• در مرحله‌ی اول $1$ خانه به جلو برود تا به خانه‌ی $2$ برسد.
• در مرحله‌ی دوم $6$ خانه به جلو برود تا به خانه‌ی $8$ برسد و بعد توسط نردبان به خانه‌ی $80$ برود.
• نهایتا پس از مراحل بالا در هر مرحله بیشترین میزانی که می‌تواند به جلو برود.

در سناریوی آخر نیز یکی از بهترین روش‌ها این است که در هر مرحله بیشترین میزانی که می‌تواند به جلو برود. دقت کنید که در این سناریو اگر استاد در خانه‌ی $5$ قرار بگیرد باید با استفاده از پله به خانه‌ی $99$ برود. سپس در آن خانه توسط مار نیش زده می‌شود و به خانه‌ی $4$ برمی‌گردد.

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

به تعدادی مربع واحد که شکلی همبند ایجاد کنند، (یعنی با شروع از هر مربع بتوان با تعدادی بار جابه‌جا شدن بین مربع‌های مجاور ضلعی به هر مربع دیگر رسید) یک چندمینو می‌گوییم. برای مثال تمام $6$-مینوهای ممکن را می‌توانید در شکل زیر (با در نظر گرفتن دوران‌ها) ببینید:

استاد که این بار سوال را صریح بیان می‌کند از شما می‌خواهد تعداد روش‌های پوشاندن یک جدول $2$ در $n$ با چندمینوها را پیدا کنید. از آن‌جایی که این مقدار ممکن است بزرگ باشد، کافی‌ست باقی‌مانده‌ی آن بر $10^9+7$ را پیدا کنید.

دو روش متفاوت شمرده می‌شود اگر در یک روش دوخانه توسط یک چندمینو پوشانده شود و در روش دیگر دو خانه در دو چندمینو قرار داشته باشند.

ورودی🔗

در خط اول ورودی عدد $t$، تعداد پرسش‌های استاد می‌آید. سپس در $t$ خط بعد در هر خط یک عدد صحیح مانند $n$، می‌آید که نشان‌دهنده تعداد ستون‌های جدول مورد پرسش استاد است.

خروجی🔗

برای هر یک از پرسش‌های استاد به‌ترتیب پاسخ را به پیمانه‌ی $10^9 + 7$ چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

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

4
1
2
962398
832984703297404324

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

2
12
290395550
469838046

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

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

سفره‌ی استاد به شکل یک مستطیل $n$ در $m$ است که در هر خانه از آن یک شکلات قرار دارد. هر یک از شکلات‌ها از یکی از انواع $1$ تا $m$ است و از آن‌جایی که استاد طرفدار مساوات است از هر نوع شکلات دقیقا $n$تا در سفره قرار داده.

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

استاد که نمی‌خواهد وضعیت سفره زیادی تغییر کند، فقط می‌تواند ترتیب شکلات‌های درون هر ستون را تغییر دهد. به بیان دیگر برای هر ستون استاد می‌تواند شکلات‌های آن ستون را به هر ترتیب دل‌خواه در همان ستون بچیند.

از آن‌جایی که استاد،‌ استاد است توانسته اثبات کند رسیدن به یک وضعیت مطلوب همواره ممکن است. اما به علت خستگی خودش نتوانسته یک وضعیت مطلوب پیدا کند. بنابراین از شما خواسته تا با ورودی گرفتن اطلاعات سفره،‌ یک وضعیت نهایی که باب میل او باشد را چاپ کنید. توجه کنید که در صورت وجود چند وضعیت مطلوب می‌توانید هر یک را به دل‌خواه چاپ کنید.

ورودی🔗

خط اول ورودی شامل دو عدد $n$ و $m$ که به ترتیب برابر تعداد سطرها و تعداد ستون‌های جدول اند می‌شود. در خط $i$-ام از $n$ خط بعدی $m$ عدد $a_{i,1}, a_{i,2}, ... a_{i,m}$ داده می‌شود که در آن $a_{i,j}$ نشان‌دهنده‌ی نوع شکلات درون خانه‌ی $(i,j)$ سفره است.

$1 \leq n,m \leq 200$ $1 \leq a_{i,j} \leq m$

خروجی🔗

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

مثال🔗

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

3 3
1 1 3
1 2 3
3 2 2

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

1 2 3
3 1 2
1 2 3

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

2 4
1 4 4 3
1 3 2 2

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

1 3 4 2
1 4 2 3