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

امین همه چیز را نصفه و نیمه می‌گوید. وقتی از او می‌پرسند اصل لانه کبوتری چیست می‌گوید: «اگر $n$ کبوتر داشته باشیم، هر طوری آن‌ها در $m$ لانه بنشینند، حتماً لانه‌ای با بیش از یک کبوتر وجود دارد.» محمدپارسا می‌گوید این حرف همیشه درست نیست.

به شما دو عدد صحیح $n$ و $m$ داده می‌شود. از شما می‌خواهیم بررسی کنید آیا به ازای این مقدار $n$ و $m$ گزاره‌ی امین درست است یا نه.

ورودی🔗

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

خروجی🔗

اگر گزاره امین برای ورودی درست بود Yes وگرنه No را خروجی دهید.

به بزرگی و کوچکی حروف توجه نمایید.

مثال🔗

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

2 6

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

No

در این نمونه، ۲ کبوتر و ۶ لانه وجود دارد. کافی‌است کبوترها مانند شکل زیر در لانه‌ها بنشینند و هیچ لانه‌ای بیش از یک کبوتر نداشته باشد و گزاره‌ی امین نادرست شود.

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

4 3

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

Yes

در این نمونه، ۴ کبوتر و ۳ لانه وجود دارد، هر طوری که کبوترها در این لانه‌ها بنشینند، حداقل یک لانه وجود دارد که در آن بیش از یک کبوتر باشد و گزاره‌ی امین درست می‌شود.

هر سطر از شکل بالای یکی از وضعیت‌های ممکن برای قرار گرفتن کبوترها در لانه‌ها را نشان می‌دهد. (تمام وضعیت‌ها مشابه یکی از ۴ حالت بالا است.) و در همه‌ی حالات یک لانه با بیش از یک کبوتر پیدا می‌شود.

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

یک مار در یک جدول $n \times m$ نشسته است. مهره‌های کمر این مار را می‌توان با اعداد $1$ (سر) تا $nm$ (دم) به ترتیب شماره‌گذاری کرد.

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

$\begin{array}{cccc} 1 & 2 & \dots & m - 1 & m \\ & & & & \\ 2m & 2m - 1 & \dots & m + 2 & m + 1 \\ & & & & \\ 2m + 1 & 2m + 2 & \dots & 3m - 1 & 3m \\ & & & & \\ . & & & & . \\ . & & & & . \\ . & & & & . \\ \end{array}$

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

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

ورودی🔗

در تنها سطر ورودی، دو عدد صحیح و مثبت $n$ و $m$ که با یک فاصله از هم جدا شده‌اند، آمده است.

$1 \leq n, m \leq 100$

خروجی🔗

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

مثال🔗

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

3 4

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

1 2 3 4
8 7 6 5
9 10 11 12

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

4 1

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

1
2
3
4

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

یک ربات داریم که در مبدا مختصات قرار دارد! هر بار ربات یک دستور می‌خواند و یک واحد بر روی صفحه مختصات دوبعدی طبق آن حرکت می‌کند. ۴ دستور ما ‍‍«بالا»، «پایین»، «چپ» و «راست» هستند.

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

به عبارت دیگر در یک عملیات نمی‌توانیم «بالا» و «پایین» را به هم و «چپ» و «راست» تبدیل کرد ولی بقیه تبدیل‌ها مجاز هستند. توجه کنید یک دستور را به تعداد دلخواه می‌توانید تغییر دهید.

برای مثال اگر دو دستور «بالا» + «چپ»‌ را داشته باشیم. می‌توانیم با یک عملیات آن را به «چپ» + «چپ» یا «راست» + «چپ» یا «بالا» + «بالا» یا «بالا» + «پایین» تبدیل کرد اما نمی‌توانیم آن را به «پایین» + «چپ» یا «بالا» + «راست» تبدیل کرد.

حال می‌خواهیم بدانیم به ازای سناریوهای مختلف و مستقل هربار ربات حداکثر چه‌ مقدار می‌تواند از مبدا دور شود!

ورودی🔗

در سطر اول ورودی $t$ یا تعداد سناریوهای مختلف می‌آید.

$1 \le t \le 100 \, 000$

در $t$ خط بعد در هر خط ۵ عدد طبیعی می‌آید. عدد اول $R$ نشانگر تعداد دستورهای راست، عدد دوم $U$ تعداد دستورهای بالا، عدد سوم $L$ تعداد دستورهای چپ و عدد چهارم $D$ تعداد دستورهای پایین است. عددد آخر $k$ هم حداکثر تعداد تغییرهای مجاز را نشان می‌دهد.

$0 \le R, U, L, D, k \le 10^9$

خروجی🔗

در $t$ سطر خروجی در هر سطر یک عدد صحیح برابر با مجذور بیشینه فاصله ممکن ربات تا مبدا را خروجی دهید.

مثال🔗

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

5
1 0 1 0 1
1 2 3 4 2
5 0 4 0 4
4 1 1 5 3
899565959 554564564 149637852 76162365 1000000000

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

2
32
41
65
2822167291196947600

در مثال اول در ابتدا یک «راست» و یک «چپ» داریم که اگر با یک تغییر «چپ» را به «بالا» عوض کنیم آنگاه یک «راست» و یک «بالا» خواهیم داشت و مجذور فاصله ما ۲ خواهد بود. با توجه به اینکه مستقیماً نمی‌توان «چپ» را تبدیل به «راست» کرد به فاصله دورتری از مبدا با یک عملیات نمی‌توان رسید.

در مثال دوم اگر با دو عملیات دو «بالا» را به دو «چپ» تبدیل کنیم آنگاه ۴ «پایین»، ۵ «چپ» و ۱ «راست» خواهیم داشت. پس ربات در نقطه $(-4,4)$ قرار خواهد گرفت و مجذور فاصله آن ۳۲ خواهد بود.

در مثال سوم اگر با ۴ عملیات هر ۴ «چپ» را به ۴ «پایین» تبدیل کنیم آنگاه ربات در نقطه $(5,-4)$ با مجذور فاصله ۴۱ از مبدا قرار خواهد گرفت.

در مثال چهارم اگر با دو عملیات تنها «بالا» را به «پایین» تبدیل کنیم (یکبار «بالا» را به «راست» و بار دیگر «راست» را به «پایین») و با یک عملیات دیگر تنها «چپ» را به «پایین» تبدیل کنیم, آنگاه ۷ «پایین» و ۴ «راست» خواهیم داشت و فاصله ما از مبدا $\sqrt {65}$ خواهد بود.

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

مارکوپولو قصد دیدن دور دنیا در ۸۰ روز را دارد. بنابرین هیچ گاه دوست ندارد شهری را بیش‌از یکبار ببیند! به طور دقیق‌تر هر کشوری که مارکوپولو به آن سفر می‌کند قابل نمایش به صورت جدولی $n \times m$ است به طوری که خانه‌های جدول شهرهای ‌کشور هستند.

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

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

ورودی🔗

در سطر اول ورودی $t$ تعداد کشورهای مورد گردش مارکو است. سپس اطلاعات $t$ کشور می‌آید. $1 \le t \le 10 \, 000$

در سطر اول اطلاعات یک کشور به ترتیب $n$ تعداد سطرها و $m$ تعداد ستون‌های جدول متناظر کشور می‌آید. $2 \le n, m \le 1000$

سپس در $n$ سطر در هر سطر $m$ عدد می‌آید که $j$امین عدد (از سمت چپ) از سطر $i$ام برابر $c_{i,j}$ ارزش شهر‌ متناظر با خانه سطر $i$ و ستون $j$ است. ($c_{1,1}$ ارزش مبدا و $c_{n,m}$ ارزش مقصد را نشان می‌دهد.) $1 \le c_{i,j} \le 10^9$

تضمین می‌شود که مجموع $nm$ برای تمام کشورهای مورد گردش مارکو از ۱۰۰۰،۰۰۰ بیشتر نمی‌شود. یعنی:

$\sum_{i = 1}^{t} n_i \times m_i \le 1000 \, 000$

خروجی🔗

در $t$ سطر در هر سطر بیشینه رضایت‌مندی ممکن برای مارکو از سفر را خروجی دهید. توجه کنید مارکو از شهر مبدا و مقصد هم کاملاً دیدن می‌کند.

مثال🔗

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

2
2 2
3 7
5 1
3 3
1 2 4
2 4 8
4 8 16

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

11
49

در مثال اول کشور به شکل زیر است:

$\begin{array}{cc} 3 & 7 \\ 5 & 1 \\ \end{array}$

دو مسیر زیر بیشتر وجود ندارد:

1. $(1, 1) \to (1, 2) \to (2, 2)$
2. $(1, 1) \to (2, 1) \to (2, 2)$

که حداکثر رضایت‌مندی برابر $3 + 7 + 1 = 11$ است.

در مثال دوم کشور به شکل زیر است:

$\begin{array}{ccc} 1 & 2 & 4 \\ 2 & 4 & 8 \\ 4 & 8 & 16 \\ \end{array}$

و مسیر با حداکثر رضایت‌مندی از مسیر زیر برابر $49$ می‌شود. $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3)$

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

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

هر آش از تعدادی رشته تشکیل شده‌است و هر رشته نیز دنباله‌ای از حروف کوچک انگلیسی است. حال رشته $B$ را می‌توان به انتهای رشته $A$ وصل کرد اگر حرف آخر $A$ برابر با حرف اول $B$ باشد. توجه کنید طول رشته حاصل از اضافه کردن $B$ به $A$ یکی کمتر از طول مجموعه آن‌ها قبل از اتصال است. مثلاً می‌توانیم ‍amazing را به quera اضافه کنیم تا queramazing به‌دست آید.

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

ورودی🔗

در سطر اول $t$ یا تعداد آش‌ها می‌آید. سپس در خطوط بعد اطلاعات $t$ آش داده می‌شود. $1 \le t \le 100 \, 000$

در سطر اول آش $i$ام $r_i$ یا تعداد رشته‌های آش $i$ام می‌آید. $1 \le |s_{i,j}| \le 1000 \, 000$

سپس در سطر $j$ام از $r_i$ سطر بعد $s_{i,j}$ رشته $j$ام آش $i$ام می‌آید. $\sum_{i, j} |s_{i,j}| \le 1000 \, 000$

خروجی🔗

در $t$ خط کمینه اندازه هر آش پس از فشرده‌سازی را به ترتیب خروجی دهید.

مثال🔗

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

3
2
shifoo
oogvey
4
quera
math
quantum
amazing
3
abc
cba
a

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

11
21
5

در آش اول می‌توان oogvey را به انتها shifoo اضافه کرد تا به shifooogvey با طول ۱۱ رسید. راه دیگری برای اتصال آن‌ها نیست و اگر دو رشته از هم جدا باشند هم مجموع طولشان ۱۲ است.

در آش سوم می‌توان ابتدا abc را به انتهای a اضافه کرد تا abc بدست آید و سپس cba را به انتها abc اضافه کرد تا abcba به طول ۵ بدست آید. می‌توان نشان داد آشی با طول کمتر نمی‌توان ساخت.

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

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

ورودی🔗

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

$1 \le n \le 100 \, 000$

در سطر $i$ام از $n$ سطر بعد در هر سطر دو عدد می‌آید که اطلاعات یکی از پوشاک خواجه فرزان را مشخص می‌کند. عدد اول $t_i$ نوع را مشخص می‌کند (اعداد ۱ و ۲ و ۳ را به ترتیب برای کلاه و تی‌شرت و شلوار فرض کنید.) و عدد دوم $c_i$ رنگ لباس را مشخص می‌کند.

$1 \le c_i \le n$

خروجی🔗

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

زیرمسئله🔗

مثال🔗

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

6
1 1
2 2
2 3
2 2
2 3
3 1

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

0

در مثال اول در همه حالات کلاه و شلوار همرنگ هستند و هیچ تیپی خز به شمار نمی‌آید.

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

9
1 1
2 1
3 1
1 5
2 5
3 5
1 9
2 9
3 9

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

6

در مثال دوم از ۳ رنگ هر ۳ نوع را داریم. پس طبق اصل ضرب برای کلاه ۳ حالت و برای تی‌شرت ۲ حالت و برای شلوار ۱ حالت داریم و پاسخ حاصل ضرب آن‌ها یعنی ۶ است.