ضرب زیر مجموعه‌ای

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

یه روز بهاری که عمو در خانه تنها نشسته بود، حوصله‌ش سر رفته بود و به دنبال سرگرمی بود. او به ازای تمام زیرمجموعه های ${1, 2, ..., n}$ ضرب اعضای آن را محاسبه کرد و میخواست آن ها را روی کاغذ یادداشت کند.

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

ورودی🔗

در تنها خط ورودی شامل عدد $n$ داده می‌شود.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n \leq 20$

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

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

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

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

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

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

+ محدودیت زمان: ۱۰ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- عمو که دیگر حال داستان سرایی ندارد، صورت سوال را بدون هیچ گونه داستانی برای شما میگوید: او یک آرایه $n$ عضوی به نام $a$ دارد که تمامی عناصر آن فرد هستند. سپس او $q$ درخواست از شما میکند که به یکی از تو فرم زیر می‌باشند. 1. اعداد $l, r, x$ به ترتیب داده می‌شوند. سپس به ازای هر $l \leq i \leq r$ مقدار عنصر $a_i$ به اندازه $x$ واحد زیاد کنید. همچنین به علت علاقه عمو به اعداد زوج، تضمین میکند که $x$ حتما زوج است. 2. اعداد $l, r$ به ترتیب داده می‌شوند. سپس شما باید به عمو ضرب $a_i$ که $l \leq i \leq r$ است را بگویید. عمو به علت کهولت سن توانایی پردازش اعداد بزرگ را ندارد، به همین علت شما کافی است جواب را باقی مانده به پیمانه $2^{20}$ بگویید. # ورودی در خط اول ورودی شامل دو عدد $n$ و $q$ است که به ترتیب نشانگر سایز آرایه و تعداد درخواست ها می‌باشد. در خط بعدی $n$ عدد داده میشود که اعداد آرایه عمو هستند. در $q$ خط بعدی در هر خط یک پرسش داده میشود. در ابتدای هر پرسش عدد $t$ می‌آید که نوع درخواست را مشخص می‌کند. سپس با توجه به نوع درخواست یکی از دو حالت زیر داده میشود 1. ```1 l r x``` که درخواست از نوع اول را نشان میدهد. 2. ```2 l r``` که درخواست از نوع دوم را نشان میدهد. # خروجی به ازای هر درخواست نوع دوم جواب را چاپ کنید. # محدودیت‌ها $$1 \leq n, q \leq 2*10^5$$ $$1 \leq ai < 2^{20}$$ $$1 \leq l \leq r \leq n$$ $$0 \leq x \leq 2^{20}$$ ## ورودی نمونه ۱ ``` 10 10 969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323 1 5 6 3034 2 1 10 2 1 9 2 1 4 1 3 6 126904 2 5 5 2 9 9 1 7 7 853094 1 4 9 1025178 2 5 8 ``` ## خروجی نمونه ۱ ``` 1045541 1012343 558151 580413 810659 527353 ```

بازم ضرب

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

عمو که دیگر حال داستان سرایی ندارد، صورت سوال را بدون هیچ گونه داستانی برای شما میگوید:

او یک آرایه $n$ عضوی به نام $a$ دارد که تمامی عناصر آن فرد هستند. سپس او $q$ درخواست از شما میکند که به یکی از تو فرم زیر می‌باشند.

اعداد $l, r, x$ به ترتیب داده می‌شوند. سپس به ازای هر $l \leq i \leq r$ مقدار عنصر $a_i$ به اندازه $x$ واحد زیاد کنید. همچنین به علت علاقه عمو به اعداد زوج، تضمین میکند که $x$ حتما زوج است.
اعداد $l, r$ به ترتیب داده می‌شوند. سپس شما باید به عمو ضرب $a_i$ که $l \leq i \leq r$ است را بگویید. عمو به علت کهولت سن توانایی پردازش اعداد بزرگ را ندارد، به همین علت شما کافی است جواب را باقی مانده به پیمانه $2^{20}$ بگویید.

ورودی🔗

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

1 l r x که درخواست از نوع اول را نشان میدهد.
2 l r که درخواست از نوع دوم را نشان میدهد.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n, q \leq 2*10^5$ $1 \leq ai < 2^{20}$ $1 \leq l \leq r \leq n$ $0 \leq x \leq 2^{20}$

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

10 10
969575 741825 24903 1047319 450475 256145 1045323 479255 810659 768323
1 5 6 3034
2 1 10
2 1 9
2 1 4
1 3 6 126904
2 5 5
2 9 9
1 7 7 853094
1 4 9 1025178
2 5 8

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای صفری، معروف به عمو، به دلیل رانندگی کاملاً ایمن خود شهرت دارد. نه تنها همیشه دقیقاً با حداکثر سرعت مجاز رانندگی می‌کند، بلکه وقتی چراغ راهنمایی از سبز به قرمز تبدیل می‌شود و او وارد تقاطع می‌شود، فوراً خودرو را متوقف می‌کند و وقتی چراغ راهنمایی از قرمز به سبز تبدیل می‌شود، فوراً با حداکثر سرعت مجاز شروع به حرکت می‌کند. عمو دارد برای سفر بعدی‌اش برنامه ریزی می‌کند که باید رانندگی کند. او مسیرش یک جاده صاف به طول $L$ واحد است و حداکثر سرعت مجاز $1$ واحد در ثانیه است. عمو در زمان $0$ رانندگی خود را آغاز خواهد کرد. جاده دارای $N$ چراغ راهنمایی به شماره $1$ تا $N$ است. چراغ راهنمایی $i$ در فاصله $x_i$ واحد از نقطه شروع قرار دارد. در زمان $0$، تمام $N$ چراغ راهنمایی به تازگی از قرمز به سبز تغییر کرده‌اند. چراغ راهنمایی $i$ بعد از $g_i$ ثانیه قرمز می‌شود، سپس بعد از $r_i$ ثانیه از قرمز به سبز تغییر می‌کند، سپس دوباره بعد از $g_i$ ثانیه قرمز می‌شود، سپس مجدداً بعد از $r_i$ ثانیه از قرمز به سبز تغییر می‌کند و به همین ترتیب ادامه می‌دهد. در این شرایط، عمو از نقطه شروع حرکت کرده و با سرعت $1$ واحد در ثانیه رانندگی خواهد کرد. اگر چراغ راهنمایی $i$ سبز باشد یا به تازگی از قرمز به سبز تغییر کرده باشد، وقتی عمو به $x_i$ می‌رسد، او متوقف نمی‌شود و با سرعت $1$ واحد در ثانیه از تقاطع عبور می‌کند. اما اگر چراغ راهنمایی $i$ قرمز باشد یا به تازگی از سبز به قرمز تغییر کرده باشد، وقتی عمو به $x_i$ می‌رسد، او تا زمانی که چراغ راهنمایی $i$ دوباره سبز شود متوقف می‌شود. وظیفه شما این است که با توجه به توصیف‌های $N$ چراغ راهنمایی، زمانی که عمو به نقطه $L$ می‌رسد را محاسبه کنید. ## ورودی - اولین خط ورودی شامل دو عدد صحیح $N$ (تعداد چراغ‌های راهنمایی) و $L$ (طول جاده) است. - هر یک از $N$ خطوط بعدی شامل سه عدد صحیح $x_i$، $g_i$، و $r_i$ است که نشان‌دهنده موقعیت چراغ راهنمایی $i$ از نقطه شروع، مدت زمان سبز بودن ($g_i$) و مدت زمان قرمز بودن ($r_i$) است. توجه داشته باشید که موقعیت‌های همه چراغ‌های راهنمایی با هم متفاوت هستند. یعنی $x_i ≠ x_j$ برای همه $i ≠ j$. $$ 1 \le N \le 10^5 $$ $$ 1 \le L \le 10^9 $$ $$ 1 \le x_i < L $$ $$ 1 \le r_i, g_i \le 10^9 $$ ## خروجی - یک خط با یک عدد صحیح که زمان رسیدن عمو به نقطه $L$ را در ثانیه‌ها نمایش می‌دهد. # مثال ## ورودی نمونه ۱ ``` 3 10 3 3 3 6 2 2 9 3 6 ``` ## خروجی نمونه ۱ ``` 19 ``` ## ورودی نمونه ۲ ``` 1 101 50 900 1 ``` ## خروجی نمونه ۲ ``` 101 ```

رانندگی ایمن عمو

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

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

عمو دارد برای سفر بعدی‌اش برنامه ریزی می‌کند که باید رانندگی کند. او مسیرش یک جاده صاف به طول $L$ واحد است و حداکثر سرعت مجاز $1$ واحد در ثانیه است. عمو در زمان $0$ رانندگی خود را آغاز خواهد کرد. جاده دارای $N$ چراغ راهنمایی به شماره $1$ تا $N$ است. چراغ راهنمایی $i$ در فاصله $x_i$ واحد از نقطه شروع قرار دارد. در زمان $0$ ، تمام $N$ چراغ راهنمایی به تازگی از قرمز به سبز تغییر کرده‌اند. چراغ راهنمایی $i$ بعد از $g_i$ ثانیه قرمز می‌شود، سپس بعد از $r_i$ ثانیه از قرمز به سبز تغییر می‌کند، سپس دوباره بعد از $g_i$ ثانیه قرمز می‌شود، سپس مجدداً بعد از $r_i$ ثانیه از قرمز به سبز تغییر می‌کند و به همین ترتیب ادامه می‌دهد.

در این شرایط، عمو از نقطه شروع حرکت کرده و با سرعت $1$ واحد در ثانیه رانندگی خواهد کرد. اگر چراغ راهنمایی $i$ سبز باشد یا به تازگی از قرمز به سبز تغییر کرده باشد، وقتی عمو به $x_i$ می‌رسد، او متوقف نمی‌شود و با سرعت $1$ واحد در ثانیه از تقاطع عبور می‌کند. اما اگر چراغ راهنمایی $i$ قرمز باشد یا به تازگی از سبز به قرمز تغییر کرده باشد، وقتی عمو به $x_i$ می‌رسد، او تا زمانی که چراغ راهنمایی $i$ دوباره سبز شود متوقف می‌شود.

وظیفه شما این است که با توجه به توصیف‌های $N$ چراغ راهنمایی، زمانی که عمو به نقطه $L$ می‌رسد را محاسبه کنید.

ورودی🔗

اولین خط ورودی شامل دو عدد صحیح $N$ (تعداد چراغ‌های راهنمایی) و $L$ (طول جاده) است.
هر یک از $N$ خطوط بعدی شامل سه عدد صحیح $x_i$ ، $g_i$ ، و $r_i$ است که نشان‌دهنده موقعیت چراغ راهنمایی $i$ از نقطه شروع، مدت زمان سبز بودن ( $g_i$ ) و مدت زمان قرمز بودن ( $r_i$ ) است.

توجه داشته باشید که موقعیت‌های همه چراغ‌های راهنمایی با هم متفاوت هستند. یعنی $x_i ≠ x_j$ برای همه $i ≠ j$ .

$1 \le N \le 10^5$ $1 \le L \le 10^9$ $1 \le x_i < L$ $1 \le r_i, g_i \le 10^9$

خروجی🔗

یک خط با یک عدد صحیح که زمان رسیدن عمو به نقطه $L$ را در ثانیه‌ها نمایش می‌دهد.

مثال🔗

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

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

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

1 101
50 900 1

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک عدد مخلوط را می‌توان توسط سه عدد طبیعی $(a\, b\, c)$ نشان داد که با $a + \frac{b}{c}$ معادل است. یک عدد مخلوط جهش یافته به صورت $(a'\, b'\, c')$ تعریف می‌شود که در آن $a'$، $b'$، $c'$ می‌توانند اعداد طبیعی یا دیگر اعداد مخلوط جهش یافته باشند. توجه کنید که یک عدد مخلوط جهش یافته معادل یک عدد کسری است. برای یک عدد مخلوط جهش یافته، می‌خواهیم که مقدار آن را به‌صورت یک کسر غیرقابل کاهش (کسری که صورت و مخرج آن نسبت به هم اول باشند) بیان کنیم. به عنوان مثال، کسر غیرقابل کاهش معادل عدد مخلوط جهش یافته $( (1\, 2\, 4)\, (5\, 2\, 3)\, (4\, 3\, (2\, 7\, 3) ) )$ به صورت زیر است: $$ \left(1 + \frac{2}{4}\right) + \displaystyle\frac{5 + \displaystyle\frac{2}{3}}{4 + \displaystyle\frac{3}{2 + \displaystyle\frac{7}{3}}} = \displaystyle\frac{991}{366} $$ درک اعداد مخلوط جهش یافته برای عمو ساده نیست. به همین دلیل از شما میخواهد که برنامه‌ای بنویسید که یک عدد مخلوط جهش یافته خوانده و سپس این عدد را به یک کسر غیرقابل کاهش تبدیل کند. # ورودی در خط اول عدد طبیعی $n$ داده می‌شود ($2 \le n \le 100$)، که $n$ تعداد کاراکترهای عدد مخلوط جهش یافته داده‌شده است. خط دوم شامل $n$ کاراکتر جداشده با فاصله است که کاراکتر ها شامل پرانتزها و اعداد بین $1$ تا $9$ هستند. توجه کنید که اعداد داده شده تک رقمی و حداقل یک هستند. # خروجی دقیقا یک خط چاپ کنید. اگر پاسخ به‌صورت $\frac{x}{y}$ باشد، خط باید شامل دو عدد صحیح $x$ و $y$ باشد که نسبت به هم اول هستند. در غیر این صورت (برای مثال، اگر ورودی معتبر نباشد)، مقدار ```-1``` را چاپ کنید. تضمین شده است که پاسخ‌ها در اعداد صحیح ۶۴-بیتی جا می‌گیرند. # محدودیت ها $$2 \leq n \leq 200$$ ## ورودی نمونه ۱ ``` 5 ( 1 2 3 ) ``` ## خروجی نمونه ۱ ``` 5 3 ``` ## ورودی نمونه ۲ ``` 8 ( 1 2 ( 3 4 5 ) ``` ## خروجی نمونه ۲ ``` -1 ``` تعداد پرانتز و بسته ها مطابقت ندارد. ## ورودی نمونه ۳ ``` 21 ( ( 1 2 4 ) ( 5 2 3 ) ( 4 3 ( 2 7 3 ) ) ) ``` ## خروجی نمونه ۳ ``` 991 366 ```

عدد مخلوط جهش یافته

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

یک عدد مخلوط را می‌توان توسط سه عدد طبیعی $(a\, b\, c)$ نشان داد که با $a + \frac{b}{c}$ معادل است. یک عدد مخلوط جهش یافته به صورت $(a'\, b'\, c')$ تعریف می‌شود که در آن $a'$ ، $b'$ ، $c'$ می‌توانند اعداد طبیعی یا دیگر اعداد مخلوط جهش یافته باشند. توجه کنید که یک عدد مخلوط جهش یافته معادل یک عدد کسری است. برای یک عدد مخلوط جهش یافته، می‌خواهیم که مقدار آن را به‌صورت یک کسر غیرقابل کاهش (کسری که صورت و مخرج آن نسبت به هم اول باشند) بیان کنیم. به عنوان مثال، کسر غیرقابل کاهش معادل عدد مخلوط جهش یافته $( (1\, 2\, 4)\, (5\, 2\, 3)\, (4\, 3\, (2\, 7\, 3) ) )$ به صورت زیر است: $\left(1 + \frac{2}{4}\right) + \displaystyle\frac{5 + \displaystyle\frac{2}{3}}{4 + \displaystyle\frac{3}{2 + \displaystyle\frac{7}{3}}} = \displaystyle\frac{991}{366}$

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

ورودی🔗

در خط اول عدد طبیعی $n$ داده می‌شود ( $2 \le n \le 100$ )، که $n$ تعداد کاراکترهای عدد مخلوط جهش یافته داده‌شده است. خط دوم شامل $n$ کاراکتر جداشده با فاصله است که کاراکتر ها شامل پرانتزها و اعداد بین $1$ تا $9$ هستند. توجه کنید که اعداد داده شده تک رقمی و حداقل یک هستند.

خروجی🔗

دقیقا یک خط چاپ کنید. اگر پاسخ به‌صورت $\frac{x}{y}$ باشد، خط باید شامل دو عدد صحیح $x$ و $y$ باشد که نسبت به هم اول هستند. در غیر این صورت (برای مثال، اگر ورودی معتبر نباشد)، مقدار -1 را چاپ کنید. تضمین شده است که پاسخ‌ها در اعداد صحیح ۶۴-بیتی جا می‌گیرند.

محدودیت ها🔗

$2 \leq n \leq 200$

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

5
( 1 2 3 )

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

5 3

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

8
( 1 2 ( 3 4 5 )

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

-1

تعداد پرانتز و بسته ها مطابقت ندارد.

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

21
( ( 1 2 4 ) ( 5 2 3 ) ( 4 3 ( 2 7 3 ) ) )

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

991 366

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو و گورو به مشکل خورده اند. داستان از جایی شروع شد که عمو از حیاط خانه شان یه درخت $n$ راسی کند و شروع به بررسی درختش کرد و متوجه شد که هر یال درختش دو حالت دارد :باز یا بسته. در ابتدا تمام یال های درخت باز بودند. او که از این قابلیت درختش شگفت زده شده بود درخت را پیش گورو برد تا باهم بازی کنند. گورو که خوشبختی رو تو تک پر بودن میدید یک مهره روی راس 1 درخت گذاشت و این بازی را روی درخت تعریف کرد: در هر نوبت بازی ، اگر در حال حاضر مهره روی یک راس با درجه 1 بود ، گورو برنده بازی می شود. در غیر این صورت ابتدا عمو یکی از یال های باز درخت را انتخاب و آن را می بندد. اگر تمام یال های درخت بسته بودند، کاری انجام نمی دهد. سپس نوبت گورو می شود. گورو در نوبت خود می تواند یکی از یال های باز متصل به راسی که مهره در آن قرار دارد را انتخاب کند و مهره به سر دیگر این یال ببرد. اگر که هیچ یک از یال های متصل به راس شامل مهره باز نبودند، عمو برنده بازی می شود. عمو که بعد از چند دست بازی همه را شکست خورده بود عصبانی شد و بعد از بحث با گورو مکان را ترک کرد. حالا که آرامشش را به دست آورده است به شما اطلاعات درخت را می دهد و از شما می پرسد که در صورتی که هر دو نفر بهینه بازی می کردند، چه کسی برنده بازی میشد؟ # ورودی خط اول ورودی شامل عدد $n$ ، تعداد رئوس درخت است. در هر یک از $n - 1$ خط بعدی ، دو عدد $u , v$ آمده است که نشانگر وجود یال بین رئوس $u$ و $v$ در درخت است. # خروجی در صورت بهینه بازی کردن دو نفر ، اگر گورو بازی را می برد 1 و اگر عمو بازی را می برد 0 خروجی دهید. # محدودیت ها $$ 1 \leq n \leq 10^5 $$ $$ 1 \leq u , v \leq n $$ ## ورودی نمونه ۱ ``` 6 1 2 2 3 2 4 1 5 5 6 ``` ## خروجی نمونه ۱ ``` 0 ``` عمو می تواند ابتدا یال بین رئوس 1 و 2 را ببندد. در این صورت گورو مجبور است مهره را به راس 5 ببرد. از آنجایی که درجه 5 بیشتر از 1 است ، پس بازی ادامه پیدا می کند. در این مرحله عمو می تواند یال بین رئوس 5 و 6 را ببندد و گورو را مجبور کند تا مهره را به راس 1 برگرداند. سپس با بستن یال بین رئوس 1 و 5 برنده بازی شود. زیرا گورو دیگر نمی تواند مهره را جابجا کند. در نتیجه عمو بازی را می برد. ## ورودی نمونه ۲ ``` 7 1 2 2 3 2 4 1 5 5 6 5 7 ``` ## خروجی نمونه ۲ ``` 1 ``` در این مثال عمو به هر نحوی بازی کند، گورو می تواند مهره را به یک راس درجه 1 برساند. در نتیجه گورو برنده می شود.

تک پر

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

عمو و گورو به مشکل خورده اند. داستان از جایی شروع شد که عمو از حیاط خانه شان یه درخت $n$ راسی کند و شروع به بررسی درختش کرد و متوجه شد که هر یال درختش دو حالت دارد :باز یا بسته. در ابتدا تمام یال های درخت باز بودند.

او که از این قابلیت درختش شگفت زده شده بود درخت را پیش گورو برد تا باهم بازی کنند. گورو که خوشبختی رو تو تک پر بودن میدید یک مهره روی راس 1 درخت گذاشت و این بازی را روی درخت تعریف کرد:

در هر نوبت بازی ، اگر در حال حاضر مهره روی یک راس با درجه 1 بود ، گورو برنده بازی می شود. در غیر این صورت ابتدا عمو یکی از یال های باز درخت را انتخاب و آن را می بندد. اگر تمام یال های درخت بسته بودند، کاری انجام نمی دهد. سپس نوبت گورو می شود. گورو در نوبت خود می تواند یکی از یال های باز متصل به راسی که مهره در آن قرار دارد را انتخاب کند و مهره به سر دیگر این یال ببرد. اگر که هیچ یک از یال های متصل به راس شامل مهره باز نبودند، عمو برنده بازی می شود.

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

ورودی🔗

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

خروجی🔗

در صورت بهینه بازی کردن دو نفر ، اگر گورو بازی را می برد 1 و اگر عمو بازی را می برد 0 خروجی دهید.

محدودیت ها🔗

$1 \leq n \leq 10^5$ $1 \leq u , v \leq n$

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

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

عمو می تواند ابتدا یال بین رئوس 1 و 2 را ببندد. در این صورت گورو مجبور است مهره را به راس 5 ببرد. از آنجایی که درجه 5 بیشتر از 1 است ، پس بازی ادامه پیدا می کند. در این مرحله عمو می تواند یال بین رئوس 5 و 6 را ببندد و گورو را مجبور کند تا مهره را به راس 1 برگرداند. سپس با بستن یال بین رئوس 1 و 5 برنده بازی شود. زیرا گورو دیگر نمی تواند مهره را جابجا کند. در نتیجه عمو بازی را می برد.

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

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

در این مثال عمو به هر نحوی بازی کند، گورو می تواند مهره را به یک راس درجه 1 برساند. در نتیجه گورو برنده می شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو پس از به ارث بردن مقدار زیادی پول به دنبال راهی برای سرمایه گذاری بود تا بتواند بیشتر درآمد داشته باشد. پس از مشورت با دوستان خود به این نتیحه رسید که مغازه‌ای باز کند و در آن مکعب روبیک بفروشد. دوست عمو برای مغازه او $k$ روبیک آورده است که هر کدام به شکل یک مکعب مربع هستند. هر مکعب شامل $ n*n*n $ مکعب $ 1*1*1 $ است که ابعاد همه آنها یکسان است. عمو برای اینکه فروش خود را بیشتر کند، سعی میکند که بعضی خانه های مجاور روبیک را به هم بچسباند به طوری که هر کدام به شکل یک روبیک با ابعاد دیگر باشد. همچنین لازم است که پس از چسباندن و تبدیل آن به روبیک با ابعاد کوچک‌تر هر تعداد چرخش مجاز در روبیک جدید قابل انجام باشد. (خانه های به هم چسبیده جدا نشوند و شکل کلی نیز از مکعب مربع خارج نشود). حال عمو از شما می‌خواهد که بگویید به ازای هر مکعب با ابعاد $n*n*n$ چند عدد $m$ وجود دارد که بتوان آن را با چسب زدن به $m*m*m$ تبدیل کرد. برای درک بهتر سوال به نمونه ورودی توجه کنید. # ورودی در خط اول ورودی شامل عدد $k$ که نشانگر تعداد روبیک های موجود در مغازه است، داده می‌شود. در $k$ خط بعدی در هر خط ابعاد هر یک از روبیک ها داده میشود. # خروجی به ازای هر روبیک بگویید که به عنوان چه روبیک هایی قابل فروختن است. # محدودیت‌ها $$1 \leq k \leq 1000$$ $$1 \leq n \leq 1000$$ ## ورودی نمونه ۱ ``` 2 3 4 ``` ## خروجی نمونه ۱ ``` 2 4 ``` مکعب ۳ در ۳ در ۳ فقط به عنوان مکعب ۳ در ۳ در ۳ و ۱ در ۱ در ۱ قابل فروش است. مکعب ۴ در ۴ در ۴ را میتوان به عنوان ۲ در ۲ در ۲ فروخت. (چسباندن خانه ها گوشه به تمامی خانه های مجاور راسی آن ها). به عنوان ۳ در ۳ در ۳ نیز میتوان فروخت، به این صورت که مرکز های مجاور را به هم میچسباند و وسط اضلاع را نیز به هم چسب میزند). به عنوان ۴ در ۴ در ۴ و ۱ در ۱ در ۱ نیز میتوان فروخت. در شکل زیر تبدیل ۴ در ۴ در ۴ به دو حالت گفته شده نشان داده شده. (خانه ها مجاور همرنگ به هم چسبیده اند). ![تبدیل های روبیک ۴ در ۴ در ۴](https://i.imgur.com/NlK1pN1.jpeg)

روبیک فروشی

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

عمو پس از به ارث بردن مقدار زیادی پول به دنبال راهی برای سرمایه گذاری بود تا بتواند بیشتر درآمد داشته باشد. پس از مشورت با دوستان خود به این نتیحه رسید که مغازه‌ای باز کند و در آن مکعب روبیک بفروشد. دوست عمو برای مغازه او $k$ روبیک آورده است که هر کدام به شکل یک مکعب مربع هستند. هر مکعب شامل $n*n*n$ مکعب $1*1*1$ است که ابعاد همه آنها یکسان است.

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

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

برای درک بهتر سوال به نمونه ورودی توجه کنید.

ورودی🔗

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

خروجی🔗

به ازای هر روبیک بگویید که به عنوان چه روبیک هایی قابل فروختن است.

محدودیت‌ها🔗

$1 \leq k \leq 1000$ $1 \leq n \leq 1000$

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

2
3
4

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

2
4

مکعب ۳ در ۳ در ۳ فقط به عنوان مکعب ۳ در ۳ در ۳ و ۱ در ۱ در ۱ قابل فروش است.

مکعب ۴ در ۴ در ۴ را میتوان به عنوان ۲ در ۲ در ۲ فروخت. (چسباندن خانه ها گوشه به تمامی خانه های مجاور راسی آن ها). به عنوان ۳ در ۳ در ۳ نیز میتوان فروخت، به این صورت که مرکز های مجاور را به هم میچسباند و وسط اضلاع را نیز به هم چسب میزند). به عنوان ۴ در ۴ در ۴ و ۱ در ۱ در ۱ نیز میتوان فروخت. در شکل زیر تبدیل ۴ در ۴ در ۴ به دو حالت گفته شده نشان داده شده. (خانه ها مجاور همرنگ به هم چسبیده اند).

تبدیل های روبیک ۴ در ۴ در ۴

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- عمو دنباله ی اعداد $A = a_1, a_2, \dots, a_N$ را از دفترچه خاطرات بچگی‌اش پیدا کرده است. در کنار این دنباله نوشته شده بود که طول بلندترین زیردنباله صعودی آن را بیابید. عمو که دیگر پیر شده بود، برای اینکه خودش را به چالش بکشد سوال را به شکل زیر عوض کرد و سعی کرد آن را حل کند. به جای بلندترین زیردنباله صعودی، بلندترین دنباله مانند $B = b_1, b_2, \dots, b_M$ را پیدا کنید که زیر دنباله دابل صعودی باشد. یعنی دو شرط زیر را داشته باشد: - دنباله‌ی $B$ یک زیردنباله از $A$ باشد. - برای تمامی $i$ ها که $1 \leq i \leq M - 2$، شرط $b_i < b_{i+2}$ برقرار باشد. یک زیر دنباله از یک دنباله به دنباله‌ای گفته می‌شود که از حذف صفر یا چند عنصر از دنباله اصلی به دست می‌آید، بدون اینکه ترتیب باقی‌مانده تغییر کند. حال عمو که این سوال را حل کرده و از آن خوشش آمده، آن را به شما نیز میدهد تا خودتان را به چالش بکشید. ## ورودی - اولین خط ورودی شامل یک عدد صحیح $N$ است که تعداد عناصر دنباله $A$ را نشان می‌دهد. - خط دوم شامل $N$ عدد صحیح است که مقادیر $a_1, a_2, \dots, a_N$ را نشان می‌دهد. هر عدد $a_i$ مقداری بین $1$ و $N$ دارد. ## خروجی یک عدد صحیح که طولانی‌ترین دنباله $B$ که شرایط فوق را برآورده می‌کند، نشان می‌دهد. ## محدودیت‌ها $$1 \le N \le 5000$$ $$1 \le A_i \le N$$ # مثال ## ورودی نمونه ۱ ``` 8 1 5 7 8 6 3 4 2 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 8 1 4 2 8 5 7 1 4 ``` ## خروجی نمونه ۲ ``` 5 ``` ## ورودی نمونه ۳ ``` 2 1 2 ``` ## خروجی نمونه ۳ ``` 2 ``` ## ورودی نمونه ۴ ``` 6 2 2 3 3 5 5 ``` ## خروجی نمونه ۴ ``` 6 ```

دابل صعودی

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

عمو دنباله ی اعداد $A = a_1, a_2, \dots, a_N$ را از دفترچه خاطرات بچگی‌اش پیدا کرده است. در کنار این دنباله نوشته شده بود که طول بلندترین زیردنباله صعودی آن را بیابید. عمو که دیگر پیر شده بود، برای اینکه خودش را به چالش بکشد سوال را به شکل زیر عوض کرد و سعی کرد آن را حل کند. به جای بلندترین زیردنباله صعودی، بلندترین دنباله مانند $B = b_1, b_2, \dots, b_M$ را پیدا کنید که زیر دنباله دابل صعودی باشد. یعنی دو شرط زیر را داشته باشد:

دنباله‌ی $B$ یک زیردنباله از $A$ باشد.
برای تمامی $i$ ها که $1 \leq i \leq M - 2$ ، شرط $b_i < b_{i+2}$ برقرار باشد.

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

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

ورودی🔗

اولین خط ورودی شامل یک عدد صحیح $N$ است که تعداد عناصر دنباله $A$ را نشان می‌دهد.
خط دوم شامل $N$ عدد صحیح است که مقادیر $a_1, a_2, \dots, a_N$ را نشان می‌دهد. هر عدد $a_i$ مقداری بین $1$ و $N$ دارد.

خروجی🔗

یک عدد صحیح که طولانی‌ترین دنباله $B$ که شرایط فوق را برآورده می‌کند، نشان می‌دهد.

محدودیت‌ها🔗

$1 \le N \le 5000$ $1 \le A_i \le N$

مثال🔗

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

8
1 5 7 8 6 3 4 2

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

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

8
1 4 2 8 5 7 1 4

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

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

2
1 2

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

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

6
2 2 3 3 5 5

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

جمعه

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

برای هر عدد طبیعی $n$ مقدار $f(n)$ را برابر مجموع ارقام آن تعریف میکنیم. برای مثال $f(114514) = 1 + 1 + 4 + 5 + 1 + 4 = 16$ . برای هر $n$ و $k$ مقدار $g(n , k)$ را برابر با $f(f(...(f(n)...))$ تعریف می کنیم که در آن تابع $f$ دقیقا $k$ بار صدا زده شده است.

عمو که بعد از دیدن این تعاریف به آن ها علاقه مند شده ، تصمیم می گیرد یه بازی هیجان انگیز به اسم جمعه انجام بدهد. او می خواهد $T$ دور جمعه بازی کند. در هر دور بازی سه عدد $N , m , k$ انتخاب می کند و باید تعداد $n$ های طبیعی را پیدا کند که $n \leq N$ و $g(n , k) = m$ باشد. عمو که فهمیده بود تنهایی از پس این بازی بر نمیاد از شما کمک می خواهد تا جواب هر دور از بازی را به پیمانه $10^9 + 7$ خروجی دهید.

ورودی🔗

در خط اول عدد $T$ ورودی داده می شود که نشانگر تعداد پرسش هاست.

در هر یک از $T$ خط بعدی به شما سه عدد طبیعی $N,k,m$ به ترتیب ورودی داده می شوند.

خروجی🔗

به ازای هر پرسش جواب آن را به پیمانه $10^9 + 7$ خروجی دهید.

محدودیت ها🔗

$1 \leq T \leq 5$ $1 \leq N \leq 10^{1000}$ $1 \leq k , m \leq 10^9$

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

2
114 1 5
514 2 10

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

8
10

در دور اول، مقدار $n$ می تواند برابر با 5 ، 14 ، 23 ، 32 ، 41 ، 50 ، 104 و 113 باشد تا $g(n,1) = 5$ برقرار باشد.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۱۰۲۴ مگابایت ---------- عمو پس از به ارث بردن مقدار زیادی پول به دنبال راهی برای سرمایه گذاری بود تا بتواند بیشتر درآمد داشته باشد. پس از مشورت با دوستان خود به این نتیحه رسید که مغازه‌ای باز کند و در آن مکعب روبیک بفروشد. پس از به دست آوردن پول هنگفتی از فروش روبیک، عمو به فکر بازنشستگی افتاده بود. برای همین به دنبال آرامش برای اندک سال‌های باقی‌مانده عمر خود بود. به همین دلیل به روستایی در شمال نقل مکان کرد. عمو پس از اینکه پول خود را بین فرزندانش تقسیم کرد، با باقی مانده آن تعدادی زمین کشاورزی خرید. هر یک از مزرعه‌های عمو به شکل یک مربع شامل $n$ در $n$ مربع واحد است که $n$ فرد است. در روستای عمو اینا پر از کلاغ بود و کلاغ‌ها علاقه به حمله به زمین ها دارند. از همین جهت عمو میخواد در زمین خود چند مترسک بکارد. اگر عمو در خانه‌ای از مزرعه‌ای به ابعاد $n*n$ مترسک بکارد، کلاغ ها دیگر به خانه‌هایی که در مربع $n*n$ ای که مترسک در مرکز آن است، حمله نمی‌کنند. به دلیل جنس متفاوت بخش های مختلف زمین هزینه کاشت مترسک در خانه واقع در تقاطع سطر $i$ و ستون $j$ برابر عدد $a_{i,j}$ است. عمو که حتی پس از بازنشستگی باز به دنبال پول بیشتر است، میخواهد با کمترین هزینه کاری کند که کلاغ ها به هیچ بخشی از هیچ کدام مزرعه‌ش حمله نکنند. برای همین از شما میخواد که بگویید کمترین هزینه برای این کار چه قدر است. # ورودی ابتدا تعداد مزرعه های عمو داده می‌شود. سپس به ازای هر مزرعه، خط اول ورودی شامل عدد **فرد** $n$ است که ابعاد مزرعه را مشخص می‌کند. در $n$ خط بعدی در هر خط $n$ عدد داده میشود که عدد $j$م در خط $i$م همان $a_{i,j}$ است. # خروجی به ازای هر مزرعه کمترین هزینه جهت راحت شدن از شر کلاغ‌ها را چاپ کنید. # محدودیت‌ها $$1 \leq n \leq 499$$ $$1 \leq a_{i,j} \leq 10^9$$ $$1 \leq \sum n^2 \leq 5*10^5$$ ## ورودی نمونه ۱ ``` 2 3 1 1 1 1 1 1 1 1 1 5 8 5 2 8 3 5 6 9 7 3 7 8 9 1 4 8 9 4 5 5 2 8 6 9 3 ``` ## خروجی نمونه ۱ ``` 1 5 ``` حالت بهینه به ازای هر مزرعه در شکل زیر آمده است. ![Minions and the Moon](https://i.imgur.com/4Snfps2.png)

مترسک

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

عمو پس از به ارث بردن مقدار زیادی پول به دنبال راهی برای سرمایه گذاری بود تا بتواند بیشتر درآمد داشته باشد. پس از مشورت با دوستان خود به این نتیحه رسید که مغازه‌ای باز کند و در آن مکعب روبیک بفروشد. پس از به دست آوردن پول هنگفتی از فروش روبیک، عمو به فکر بازنشستگی افتاده بود. برای همین به دنبال آرامش برای اندک سال‌های باقی‌مانده عمر خود بود. به همین دلیل به روستایی در شمال نقل مکان کرد.

عمو پس از اینکه پول خود را بین فرزندانش تقسیم کرد، با باقی مانده آن تعدادی زمین کشاورزی خرید. هر یک از مزرعه‌های عمو به شکل یک مربع شامل $n$ در $n$ مربع واحد است که $n$ فرد است. در روستای عمو اینا پر از کلاغ بود و کلاغ‌ها علاقه به حمله به زمین ها دارند. از همین جهت عمو میخواد در زمین خود چند مترسک بکارد. اگر عمو در خانه‌ای از مزرعه‌ای به ابعاد $n*n$ مترسک بکارد، کلاغ ها دیگر به خانه‌هایی که در مربع $n*n$ ای که مترسک در مرکز آن است، حمله نمی‌کنند.

به دلیل جنس متفاوت بخش های مختلف زمین هزینه کاشت مترسک در خانه واقع در تقاطع سطر $i$ و ستون $j$ برابر عدد $a_{i,j}$ است. عمو که حتی پس از بازنشستگی باز به دنبال پول بیشتر است، میخواهد با کمترین هزینه کاری کند که کلاغ ها به هیچ بخشی از هیچ کدام مزرعه‌ش حمله نکنند. برای همین از شما میخواد که بگویید کمترین هزینه برای این کار چه قدر است.

ورودی🔗

ابتدا تعداد مزرعه های عمو داده می‌شود.

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

در $n$ خط بعدی در هر خط $n$ عدد داده میشود که عدد $j$ م در خط $i$ م همان $a_{i,j}$ است.

خروجی🔗

به ازای هر مزرعه کمترین هزینه جهت راحت شدن از شر کلاغ‌ها را چاپ کنید.

محدودیت‌ها🔗

$1 \leq n \leq 499$ $1 \leq a_{i,j} \leq 10^9$ $1 \leq \sum n^2 \leq 5*10^5$

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

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

1
5

حالت بهینه به ازای هر مزرعه در شکل زیر آمده است.

Minions and the Moon

نقاشی بکش، نقاشی بکش، عمو

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

عمو پس از بازنشستگی درکنار مزرعه‌داری به سراغ نقاشی رفت. او یک کاغذ که به مربع های واحد تقسیم شده بود را برداشت. سپس $n$ مربع از آن را انتخاب کرد. $i$ م مربع دارای مختصات $(x_i, y_i)$ بود. سپس هر کدام از آن‌ها را به یکی از دو رنگ آبی و قرمز رنگ کرد به طوری که حتما در هر ستون حداکثر یک قرمز و در هر سطر حداکثر یک آبی باشد.

برای مثال شکل زیر یک رنگ آمیزی ممکن عمو است: رنگ آمیزی معتبر

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

ورودی🔗

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

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n \leq 2*10^5$ $-10^9 \leq x_i, y_i \leq 10^9$

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

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

این ورودی همان تصویر داخل متن سوال است.

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

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

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- عمو یک ماتریس $2 \times n$ از اعداد طبیعی $M$ دارد. همچنین او تضمین می‌کند که اعداد در هر سطر ماتریس $M$ از یکدیگر متمایز هستند. برای سطر $i$ام از $M$ ($i = 1, 2$)، $s_i$ را برابر بیشترین مجموع اعضا یک زیر دنباله صعودی از اعداد سطر $i$م تعریف میکنیم. به عنوان مثال، اگر $M$ به صورت زیر باشد: \[ \begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 2 & 3 & 5 & 4 & 1 \\ \end{bmatrix} \] آنگاه $s_1 = 1 + 2 + 3 + 4 + 5 + 6$ و $s_2 = 2 + 3 + 5$ خواهد بود. به ازای هر ماتریس $M$ مجموع $s_1 + s_2$ به عنوان قیمت آن درنظر گرفته می‌شود. پس قیمت ماتریس بالا $31$ است. حال عمو که بسیار تجملاتی است، دوست دارد که ماتریسش بیشترین قیمت را داشته باشد. برای همین او میخواد ترتیب ستون های ماتریسش را به نحوی عوض کند که قیمت ماتریسش بیشینه مقدار ممکن شود. برای مثال، اگر ستون‌های ماتریس مثال قبل $ M = [ c_1, c_2, c_3, c_4, c_5, c_6 ]$ به $ M = [c_2, c_3, c_4, c_5, c_6, c_1] $ تغییر کند، ماتریس جدید به صورت زیر خواهد بود: \[ \begin{bmatrix} 2 & 3 & 4 & 5 & 6 & 1 \\ 2 & 3 & 5 & 4 & 1 & 6 \\ \end{bmatrix} \] و قیمت آن برابر $36$ خواهد بود. یک برنامه بنویسید که به عمو بیشینه قیمت ماتریس را در بین تمام جایگشت‌های ممکن ستون‌های ماتریس $M$ محاسبه کند. ## ورودی - در خط اول ورودی شامل یک عدد طبیعی $n$ است که برابر تعداد ستون‌های ماتریس $M$ است می‌آید. - دو خط بعدی هرکدام شامل $n$ عدد صحیح هستند که عناصر سطر اول و دوم ماتریس $M$ را تشکیل می‌دهند. اعداد داده‌شده در بازه $[1, 50000]$ قرار دارند و در هر سطر اعداد متمایز هستند. ## خروجی یک خط که بیشینه قیمت در بین تمامی جایگشت‌های ممکن ستون‌های $M$ چاپ می‌کند. ## محدودیت‌ها $$1 \leq n \leq 10^4$$ # مثال ## ورودی نمونه ۱ ``` 6 1 2 3 4 5 6 6 2 3 5 4 1 ``` ## خروجی نمونه ۱ ``` 36 ``` ## ورودی نمونه ۲ ``` 5 50 40 3 2 1 1 2 3 100 200 ``` ## خروجی نمونه ۲ ``` 396 ```

ماتریس لاکچری

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

عمو یک ماتریس $2 \times n$ از اعداد طبیعی $M$ دارد. همچنین او تضمین می‌کند که اعداد در هر سطر ماتریس $M$ از یکدیگر متمایز هستند.

برای سطر $i$ ام از $M$ ( $i = 1, 2$ )، $s_i$ را برابر بیشترین مجموع اعضا یک زیر دنباله صعودی از اعداد سطر $i$ م تعریف میکنیم. به عنوان مثال، اگر $M$ به صورت زیر باشد: $\begin{bmatrix} 1 & 2 & 3 & 4 & 5 & 6 \\ 6 & 2 & 3 & 5 & 4 & 1 \\ \end{bmatrix}$ آنگاه $s_1 = 1 + 2 + 3 + 4 + 5 + 6$ و $s_2 = 2 + 3 + 5$ خواهد بود. به ازای هر ماتریس $M$ مجموع $s_1 + s_2$ به عنوان قیمت آن درنظر گرفته می‌شود. پس قیمت ماتریس بالا $31$ است.

حال عمو که بسیار تجملاتی است، دوست دارد که ماتریسش بیشترین قیمت را داشته باشد. برای همین او میخواد ترتیب ستون های ماتریسش را به نحوی عوض کند که قیمت ماتریسش بیشینه مقدار ممکن شود.

برای مثال، اگر ستون‌های ماتریس مثال قبل $M = [ c_1, c_2, c_3, c_4, c_5, c_6 ]$ به $M = [c_2, c_3, c_4, c_5, c_6, c_1]$ تغییر کند، ماتریس جدید به صورت زیر خواهد بود: $\begin{bmatrix} 2 & 3 & 4 & 5 & 6 & 1 \\ 2 & 3 & 5 & 4 & 1 & 6 \\ \end{bmatrix}$ و قیمت آن برابر $36$ خواهد بود.

یک برنامه بنویسید که به عمو بیشینه قیمت ماتریس را در بین تمام جایگشت‌های ممکن ستون‌های ماتریس $M$ محاسبه کند.

ورودی🔗

در خط اول ورودی شامل یک عدد طبیعی $n$ است که برابر تعداد ستون‌های ماتریس $M$ است می‌آید.
دو خط بعدی هرکدام شامل $n$ عدد صحیح هستند که عناصر سطر اول و دوم ماتریس $M$ را تشکیل می‌دهند. اعداد داده‌شده در بازه $[1, 50000]$ قرار دارند و در هر سطر اعداد متمایز هستند.

خروجی🔗

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

محدودیت‌ها🔗

$1 \leq n \leq 10^4$

مثال🔗

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

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

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

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

5
50 40 3 2 1
1 2 3 100 200