+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- دو تیم «استقلال» و «پرسپولیس» باهم دو بازی **رفت** و **برگشت** انجام داده‌اند. ![توضیح تصویر](https://quera.org/qbox/view/dNZzPQA6hp/A-1.png) در بازی رفت، «پرسپولیس» میزبان است و $a$ گل «پرسپولیس» به «استقلال» زده و $b$ گل «استقلال» به «پرسپولیس» زده است. در بازی برگشت، «استقلال» میزبان است و $c$ گل «پرسپولیس» به «استقلال» زده و $d$ گل «استقلال» به «پرسپولیس» زده است. حال می‌خواهیم نتیجه نهایی این دو بازی را بررسی کنیم: + تیمی کل این دو بازی را برده که مجموع گل زده‌ی بیشتری داشته باشد. + اگر مجموع گل‌های زده برابر بود تیمی برنده است که گل زده بیشتری در بازی با میزبان داشته باشد. + اگر تعداد گل‌های زده در بازی با میزبان هم برابر بود، نتیجه به «پنالتی» کشیده می‌شود. # ورودی در سطر اول ورودی عدد صحیح و مثبت $t$ آمده است، که تعداد ورودی‌های نمونه را نشان می‌دهد. $$1 \leq t \leq 1000$$ در $t$ سطر بعدی،‌ در هر سطر ۴ عدد صحیح و نامنفی $a_i$، $b_i$، $c_i$ و $d_i$ داده می‌شود، که به ترتیب نشان‌دهنده‌ی گل‌های زده تیم‌های «پرسپولیس» و «استقلال» در بازی‌های رفت و برگشت است. $$0 \leq a_i, b_i, c_i, d_i \leq 6$$ # خروجی خروجی شامل $t$ سطر است، در سطر $i$ام خروجی نتیجه بازی $i$ام چاپ می‌شود. اگر در نتیجه نهایی این دو بازی: + اگر «پرسپولیس» برنده است، عبارت `perspolis` + اگر «استقلال» برنده است، عبارت `esteghlal` + اگر که هیچ‌کدام از دو حالت قبل اتفاق نیفتاد، عبارت `penalty` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 5 6 0 0 0 0 0 0 4 1 2 1 0 1 0 1 2 1 2 2 1 ``` ## خروجی نمونه ۱ ``` perspolis esteghlal esteghlal perspolis penalty ``` <details class="blue"> <summary> **توضیحات تست اول** </summary> + نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۶ به نفع «پرسپولیس» به پایان رسیده است. + نتیجه بازی برگشت (به میزبانی «استقلال»): ۰-۰ برابر به پایان رسیده است. پس نتیجه نهایی این دو بازی ۰-۶ به نفع «پرسپولیس» (`perspolis`) است. </details> <details class="blue"> <summary> **توضیحات تست دوم** </summary> + نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۰ برابر به پایان رسیده است. + نتیجه بازی برگشت (به میزبانی «استقلال»): ۴-۰ به نفع «استقلال» به پایان رسیده است. پس نتیجه نهایی این دو بازی ۴-۰ به نفع «استقلال» (`esteghlal`) است. </details> <details class="blue"> <summary> **توضیحات تست سوم** </summary> + نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۲-۱ به نفع «استقلال» به پایان رسیده است. + نتیجه بازی برگشت (به میزبانی «استقلال»): ۰-۱ به نفع «پرسپولیس» به پایان رسیده است. مجموع گل‌های زده «پرسپولیس» و «استقلال» در هر دو بازی برابر ۲ است. اما «استقلال» ۲ گل زده در زمین «پرسپولیس» دارد ولی «پرسپولیس» ۱ گل زده در زمین «استقلال» دارد، پس برنده نهایی بازی «استقلال» (`esteghlal`) است. </details> <details class="blue"> <summary> **توضیحات تست چهارم** </summary> + نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۱ به نفع «پرسپولیس» به پایان رسیده است. + نتیجه بازی برگشت (به میزبانی «استقلال»): ۲-۱ به نفع «استقلال» به پایان رسیده است. مجموع گل‌های زده «پرسپولیس» و «استقلال» در هر دو بازی برابر ۲ است. اما «پرسپولیس» ۱ گل زده در زمین «استقلال» دارد ولی «استقلال» ۰ گل زده در زمین «پرسپولیس» دارد، پس برنده نهایی بازی «پرسپولیس» (`perspolis`) است. </details> <details class="blue"> <summary> **توضیحات تست پنجم** </summary> + نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۲-۱ به نفع «استقلال» به پایان رسیده است. + نتیجه بازی برگشت (به میزبانی «استقلال»): ۱-۲ به نفع «پرسپولیس» به پایان رسیده است. مجموع گل‌های زده هر دو تیم برابر ۳ است. گل‌های زده هر دو تیم در زمین حریف برابر ۲ است. پس باید نتیجه نهایی به «پنالتی» (`penalty`) کشیده شود. </details>

جمع فوتبالی

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

دو تیم «استقلال» و «پرسپولیس» باهم دو بازی رفت و برگشت انجام داده‌اند.

توضیح تصویر

در بازی رفت، «پرسپولیس» میزبان است و $a$ گل «پرسپولیس» به «استقلال» زده و $b$ گل «استقلال» به «پرسپولیس» زده است.

در بازی برگشت، «استقلال» میزبان است و $c$ گل «پرسپولیس» به «استقلال» زده و $d$ گل «استقلال» به «پرسپولیس» زده است.

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

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

ورودی🔗

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

$1 \leq t \leq 1000$

در $t$ سطر بعدی،‌ در هر سطر ۴ عدد صحیح و نامنفی $a_i$ ، $b_i$ ، $c_i$ و $d_i$ داده می‌شود، که به ترتیب نشان‌دهنده‌ی گل‌های زده تیم‌های «پرسپولیس» و «استقلال» در بازی‌های رفت و برگشت است.

$0 \leq a_i, b_i, c_i, d_i \leq 6$

خروجی🔗

خروجی شامل $t$ سطر است، در سطر $i$ ام خروجی نتیجه بازی $i$ ام چاپ می‌شود.

اگر در نتیجه نهایی این دو بازی:

اگر «پرسپولیس» برنده است، عبارت perspolis
اگر «استقلال» برنده است، عبارت esteghlal
اگر که هیچ‌کدام از دو حالت قبل اتفاق نیفتاد، عبارت penalty

را چاپ کنید.

مثال🔗

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

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

perspolis
esteghlal
esteghlal
perspolis
penalty

توضیحات تست اول

نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۶ به نفع «پرسپولیس» به پایان رسیده است.
نتیجه بازی برگشت (به میزبانی «استقلال»): ۰-۰ برابر به پایان رسیده است.

پس نتیجه نهایی این دو بازی ۰-۶ به نفع «پرسپولیس» (perspolis) است.

توضیحات تست دوم

نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۰ برابر به پایان رسیده است.
نتیجه بازی برگشت (به میزبانی «استقلال»): ۴-۰ به نفع «استقلال» به پایان رسیده است.

پس نتیجه نهایی این دو بازی ۴-۰ به نفع «استقلال» (esteghlal) است.

توضیحات تست سوم

نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۲-۱ به نفع «استقلال» به پایان رسیده است.
نتیجه بازی برگشت (به میزبانی «استقلال»): ۰-۱ به نفع «پرسپولیس» به پایان رسیده است.

مجموع گل‌های زده «پرسپولیس» و «استقلال» در هر دو بازی برابر ۲ است. اما «استقلال» ۲ گل زده در زمین «پرسپولیس» دارد ولی «پرسپولیس» ۱ گل زده در زمین «استقلال» دارد، پس برنده نهایی بازی «استقلال» (esteghlal) است.

توضیحات تست چهارم

نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۰-۱ به نفع «پرسپولیس» به پایان رسیده است.
نتیجه بازی برگشت (به میزبانی «استقلال»): ۲-۱ به نفع «استقلال» به پایان رسیده است.

مجموع گل‌های زده «پرسپولیس» و «استقلال» در هر دو بازی برابر ۲ است. اما «پرسپولیس» ۱ گل زده در زمین «استقلال» دارد ولی «استقلال» ۰ گل زده در زمین «پرسپولیس» دارد، پس برنده نهایی بازی «پرسپولیس» (perspolis) است.

توضیحات تست پنجم

نتیجه بازی رفت (به میزبانی «پرسپولیس»): ۲-۱ به نفع «استقلال» به پایان رسیده است.
نتیجه بازی برگشت (به میزبانی «استقلال»): ۱-۲ به نفع «پرسپولیس» به پایان رسیده است.

مجموع گل‌های زده هر دو تیم برابر ۳ است. گل‌های زده هر دو تیم در زمین حریف برابر ۲ است. پس باید نتیجه نهایی به «پنالتی» (penalty) کشیده شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک آزمون با $n$ سوال تستی چهار گزینه‌ای برگزار شده است. می‌خواهیم سامانه‌ای برای تشخیص نمره افراد بنویسیم. برای تصحیح، کلید آزمون و تصویر پاسخ‌برگ‌ها داده می‌شود. از شما می‌خواهیم نمره این پاسخ‌برگ‌ها را محاسبه کنید. ![توضیح تصویر](https://quera.org/qbox/view/GyEWwy1b9C/B-1.png) کلید آزمون یک رشته $n$ حرفی است که حروف آن `A`، `B`، `C` یا `D` است. که حرف $i$ام این رشته گزینه صحیح سوال $i$ام را نشان می‌دهد. تصویر یک پاسخ‌برگ به صورت یک جدول $n \times 4$ است. سطر $i$ام این جدول مربوط به سوال $i$ام است و در آن چهار کاراکتر قرار دارد که هر کدام به صورت `#` یا `O` است. وضعیت `#` برای یک گزینه یعنی خانه‌ی مربوط به این گزینه علامت خورده است. وضعیت `O` یعنی خانه مربوط به این گزینه علامت نخورده است. کاراکتر اول این سطر برای گزینه `A`، کاراکتر دوم برای گزینه `B`، کاراکتر سوم برای گزینه `C` و کاراکتر چهارم برای گزینه `D` است. + زمانی پاسخ یک سوال **«درست»** داده شده که فقط گزینه درست علامت خورده باشد. + زمانی پاسخ یک سوال **«نزده»** در نظر گرفته می‌شود که هیچ گزینه‌ای علامت نخورده باشد. + در صورتی که پاسخ یک سوال نه درست باشد نه نزده، پاسخ سوال **«نادرست»** در نظر گرفته می‌شود. (یعنی اگر گزینه‌ی نادرست انتخاب شود یا چندگزینه علامت خورده باشد، نادرست در نظر گرفته می‌شود.) اگر تعداد پاسخ‌های «درست» یک پاسخ‌برگ برابر $t$ و تعداد پاسخ‌های «نادرست» برابر $f$ باشد، نمره این پاسخ‌برگ برابر است با: $$3 \times t - f$$ کلید آزمون و تصویر $k$ پاسخ‌برگ به شما داده می‌شود. از شما می‌خواهیم نمره این $k$ پاسخ‌برگ را محاسبه کنید. # ورودی در سطر اول ورودی عدد صحیح و مثبت $n$ داده می‎‌شود که نشان‌دهنده‌ی تعداد سوالات آزمون است. $$1 \le n \le 20$$ در سطر دوم ورودی یک رشته به طول $n$ مانند $s_1, s_2, s_3, \dots, s_n \,$ داده می‌شود که $s_i \in \{ A, B, C, D \}$، پاسخ صحیح به پرسش $i$ام را نشان می‌دهد. در سطر سوم ورودی، عدد صحیح و مثبت $k$ داده می‎‌شود که نشان‌دهنده‌ی تعداد پاسخ‌برگ‌هایی است که داده می‌شود. $$1 \le k \le 300$$ و در $k.n$ سطر بعدی تصاویر پاسخ‌برگ‌ها را مطابق توضیحات سوال داده‌می‌شود. # خروجی خروجی شامل $k$ سطر است که عدد چاپ شده در سطر $i$ام نمره پاسخ‌برگ $i$ام را نشان می‌دهد. # مثال‌ها ## ورودی نمونه ۱ ``` 1 C 4 OO#O OOOO #OOO OO## ``` ## خروجی نمونه ۱ ``` 3 0 -1 -1 ``` آزمون ۱ سوال دارد و ۴ پاسخ‌برگ داریم که تصحیح کنیم. + پاسخ‌برگ اول، گزینه درست را علامت زده، پس ۳ نمره دریافت می‌کند. + پاسخ‌برگ‌دوم، هیچ گزینه‌ای را علامت نزده، پس ۰ نمره دریافت می‌کند. + پاسخ‌برگ سوم، گزینه‌ی اشتباه را علامت زده، پس ۱- نمره دریافت می‌کند. + پاسخ‌برگ چهارم، دو گزینه را علامت زده، پس ۱- نمره دریافت می‌کند. ## ورودی نمونه ۲ ``` 10 AABBDCABCD 1 #OOO #OOO O#OO O#OO OOO# OO#O #OOO O#OO OO#O OOO# ``` ## خروجی نمونه ۲ ``` 30 ``` آزمون ۱۰ سوال دارد و ۱ پاسخ‌برگ داریم که تصحیح کنیم. این پاسخ‌برگ به هر ۱۰ سوال پاسخ درست داده است، پس نمره دریافتی آن ۳۰ خواهد بود.

آزمون تستی

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

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

توضیح تصویر

کلید آزمون یک رشته $n$ حرفی است که حروف آن A، B، C یا D است. که حرف $i$ ام این رشته گزینه صحیح سوال $i$ ام را نشان می‌دهد.

تصویر یک پاسخ‌برگ به صورت یک جدول $n \times 4$ است. سطر $i$ ام این جدول مربوط به سوال $i$ ام است و در آن چهار کاراکتر قرار دارد که هر کدام به صورت # یا O است. وضعیت # برای یک گزینه یعنی خانه‌ی مربوط به این گزینه علامت خورده است. وضعیت O یعنی خانه مربوط به این گزینه علامت نخورده است. کاراکتر اول این سطر برای گزینه A، کاراکتر دوم برای گزینه B، کاراکتر سوم برای گزینه C و کاراکتر چهارم برای گزینه D است.

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

اگر تعداد پاسخ‌های «درست» یک پاسخ‌برگ برابر $t$ و تعداد پاسخ‌های «نادرست» برابر $f$ باشد، نمره این پاسخ‌برگ برابر است با: $3 \times t - f$

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

ورودی🔗

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

$1 \le n \le 20$

در سطر دوم ورودی یک رشته به طول $n$ مانند $s_1, s_2, s_3, \dots, s_n \,$ داده می‌شود که $s_i \in \{ A, B, C, D \}$ ، پاسخ صحیح به پرسش $i$ ام را نشان می‌دهد.

در سطر سوم ورودی، عدد صحیح و مثبت $k$ داده می‎‌شود که نشان‌دهنده‌ی تعداد پاسخ‌برگ‌هایی است که داده می‌شود. $1 \le k \le 300$

و در $k.n$ سطر بعدی تصاویر پاسخ‌برگ‌ها را مطابق توضیحات سوال داده‌می‌شود.

خروجی🔗

خروجی شامل $k$ سطر است که عدد چاپ شده در سطر $i$ ام نمره پاسخ‌برگ $i$ ام را نشان می‌دهد.

مثال‌ها🔗

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

1
C
4
OO#O
OOOO
#OOO
OO##

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

3
0
-1
-1

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

پاسخ‌برگ اول، گزینه درست را علامت زده، پس ۳ نمره دریافت می‌کند.
پاسخ‌برگ‌دوم، هیچ گزینه‌ای را علامت نزده، پس ۰ نمره دریافت می‌کند.
پاسخ‌برگ سوم، گزینه‌ی اشتباه را علامت زده، پس ۱- نمره دریافت می‌کند.
پاسخ‌برگ چهارم، دو گزینه را علامت زده، پس ۱- نمره دریافت می‌کند.

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

10
AABBDCABCD
1
#OOO
#OOO
O#OO
O#OO
OOO#
OO#O
#OOO
O#OO
OO#O
OOO#

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

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

این پاسخ‌برگ به هر ۱۰ سوال پاسخ درست داده است، پس نمره دریافتی آن ۳۰ خواهد بود.

کسر لتکی

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

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

$1+\frac{2+\frac{4 + \dots}{5 + \dots}}{3+\frac{6 + \dots}{7 + \dots}}$

از شما می‌خواهیم برنامه‌ای بنویسید که «کد لتک» ( $LaTeX$ ) این کسر را بعد از $n$ مرحله باز شدن، چاپ کند.

توضیح تصویر

برای ایجاد کسر به شکل $\frac{a}{b}$ ، از دستور \frac{a}{b} استفاده می‌کنیم. همچنین می‌توانیم در صورت یک کسر، یک کسر دیگر تعریف کنیم.

برای فهم بهتر سوال به مثال‌های نمونه مراجعه کنید.

ورودی🔗

در تنها سطر ورودی عدد صحیح و مثبت $n$ داده می‌شود.

$1 \leq n \leq 10$

خروجی🔗

یک رشته بدون فاصله چاپ کنید که «کد لتک» کسر فوق را بعد از $n$ مرحله باز شدن، چاپ کند.

مثال🔗

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

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

$1$

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

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

1+\frac{2}{3}

$1+\frac{2}{3}$

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

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

1+\frac{2+\frac{4}{5}}{3+\frac{6}{7}}

$1+\frac{2+\frac{4}{5}}{3+\frac{6}{7}}$

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

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

1+\frac{2+\frac{4+\frac{8}{9}}{5+\frac{10}{11}}}{3+\frac{6+\frac{12}{13}}{7+\frac{14}{15}}}

$1+\frac{2+\frac{4+\frac{8}{9}}{5+\frac{10}{11}}}{3+\frac{6+\frac{12}{13}}{7+\frac{14}{15}}}$

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کوئرا در راستای توسعه‌ی محصولات خود، یک فرودگاه راه‌اندازی کرده است. از شما می‌خواهیم برنامه‌ای بنویسید تا بتواند بخشی از دستورات برج مراقبت را انجام دهد. ![توضیح تصویر](https://quera.org/qbox/view/NXJm3q9dya/D-1.png) این فرودگاه $k$ باند پرواز، برای بلند شدن (`take-off`) یا فرود آمدن (`landing`) هواپیماها دارد. این $k$ باند از ۱ تا $k$ شماره گذاری شده‌اند. هر هواپیما یک رشته به طول ۱۰ و یکتا از ارقام به نام `<ID>` دارد که آن هواپیما را به صورت یکتا مشخص می‌کند. در هر لحظه، هر هواپیما، یکی از چهار وضعیت زیر را دارد: 1. در فرودگاه کوئرا است و هیچ باندی را اشغال نکرده است. 2. در فرودگاه کوئرا است ولی یکی از باندها را اشغال کرده و در حال بلند شدن است. 3. در فرودگاه کوئرا است ولی یکی از باندها را اشغال کرده و در حال فرود آمدن است. 4. در فرودگاه کوئرا نیست. (یعنی این هواپیما تا کنون دیده نشده یا از همین فرودگاه به پرواز در آمده است.) می‌دانیم در ابتدا $n$ هواپیما در فرودگاه کوئرا است (وضعیت ۱) و `<ID>` همه‌ی این $n$ هواپیما را داریم. برای برج مراقبت این فرودگاه چندین دستور می‌آید که از شما می‌خواهیم به آن‌ها رسیدگی کنید. هر دستور به یکی از فرمت‌های زیر است. <details class="green"> <summary> **دستور `TAKE-OFF`** </summary> ``` TAKE-OFF <ID> ``` این دستور یعنی هواپیمای با آی‌دی `<ID>` قصد بلندشدن از فرودگاه را دارد. + اگر این هواپیما در وضعیت `4` است پیام `YOU ARE NOT HERE` را چاپ کنید. + اگر این هواپیما در وضعیت `3` است پیام `YOU ARE LANDING NOW` را چاپ کنید. + اگر این هواپیما در وضعیت `2` است پیام `YOU ARE TAKING OFF` را چاپ کنید. + اگر این هواپیما در وضعیت `1` است ولی هیچ باند خالی نداریم پیام `NO FREE BOUND` را چاپ کنید. + در صورتی که هیچ کدام از اتفاقات بالا نیفتاد ابتدا وضعیت هواپیما را به `2` تغییر دهید و سپس هواپیما را به اولین (کم‌ترین شماره) باند خالی انتقال دهید تا بلند شود. </details> <details class="green"> <summary> **دستور `LANDING`** </summary> ``` LANDING <ID> ``` این دستور یعنی هواپیمای با آی‌دی `<ID>` قصد نشستن در فرودگاه را دارد. + اگر این هواپیما در وضعیت `1` است پیام `YOU ARE HERE` را چاپ کنید. + اگر این هواپیما در وضعیت `2` است پیام `YOU ARE TAKING OFF` را چاپ کنید. + اگر این هواپیما در وضعیت `3` است پیام `YOU ARE LANDING NOW` را چاپ کنید. + اگر این هواپیما در وضعیت `4` است ولی هیچ باند خالی نداریم پیام `NO FREE BOUND` را چاپ کنید. + در صورتی که هیچ کدام از اتفاقات بالا نیفتاد ابتدا وضعیت هواپیما را به `3` تغییر دهید و سپس هواپیما را به آخرین (بزرگ‌ترین شماره) باند خالی انتقال دهید تا فرود بیاید. </details> <details class="green"> <summary> **دستور `PLANE-STATUS`** </summary> ``` PLANE-STATUS <ID> ``` این دستور وضعیت هواپیمای با آی‌دی `<ID>` را در این لحظه درخواست می‌کند و شما باید شماره وضعیت این هواپیما را چاپ کنید. </details> <details class="green"> <summary> **دستور `BAND-STATUS`** </summary> ``` BAND-STATUS <LINE> ``` این دستور وضعیت باند `<LINE>` را در این لحظه درخواست می‌کند و شما باید آی‌دی هواپیمایی که در این خط هست را چاپ کنید و اگر این باند آزاد است و هواپیمایی در آن نیست کلمه `FREE` را چاپ کنید. </details> # ورودی در سطر اول ورودی دو عدد صحیح $n$ و $k$ آمده است که به ترتیب نشان‌دهنده‌ی تعداد هواپیماهای داخل فرودگاه کوئرا و تعداد باند‌های فرودگاه کوئرا است. $$1 \le n, k \le 100$$ در $n$ سطر بعدی در هر سطر یک رشته ۱۰ رقمی که نشان‌دهنده‌ی آی‌دی هواپیماهای داخل فرودگاه است. در سطر بعدی عدد صحیح $q$ آمده است که نشان‌دهنده‌ی تعداد دستورات است. $$1 \le q \le 1000$$ سپس در هر کدام از $q$ سطر بعدی یکی از دستورهای توضیح داده شده در کادر می‌آید. # خروجی خروجی شامل حداکثر $q$ سطر است که در سطر $i$ام خروجی متناسب با دستورها را چاپ می‌شود. # مثال ## ورودی نمونه ۱ ``` 3 4 0000000001 0000000002 0000000003 5 TAKE-OFF 0000000001 LANDING 0000000004 PLANE-STATUS 0000000001 BAND-STATUS 4 LANDING 0000000002 ``` ## خروجی نمونه ۱ ``` 2 0000000004 YOU ARE HERE ``` <details class="blue"> <summary> **توضیحات نمونه ۱** </summary> در ابتدا ۳ هواپیما با آی‌دی‌های `0000000001`، `0000000002` و `0000000003` در فرودگاه کوئرا قرار دارند. ۴ باند در این فرودگاه داریم که در ابتدا هر ۴تای آن‌ها خالی هستند. + در دستور اول هواپیمای `0000000001` قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۱ شود. (اولین باند خالی است.) + در دستور دوم هواپیمای `0000000004` قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۴ فرود بیاید. (آخرین باند خالی است) + در دستور سوم وضعیت هواپیمای `0000000001` پرسیده می‌شود. این هواپیما در وضعیت ۲ (در حال بلند شدن) قرار دارد. پس عدد ۲ چاپ می‌شود. + دستور چهارم وضعیت باند ۴ پرسیده می‌شود. در این باند هواپیمای `0000000004` قرار دارد و باید رشته `0000000004` چاپ شود. + در دستور پنجم هواپیمای `0000000002` قصد فرود آمدن در فرودگاه کوئرا را دارد ولی این هواپیما اکنون در فرودگاه کوئرا است؛ پس باید پیام `YOU ARE HERE` چاپ شود. </details> ## ورودی نمونه ۲ ``` 2 5 1000000000 0002000000 10 TAKE-OFF 0002000000 LANDING 1234567891 PLANE-STATUS 1234567891 BAND-STATUS 5 LANDING 9876543219 LANDING 5555555555 BAND-STATUS 2 TAKE-OFF 1000000000 LANDING 3434343434 PLANE-STATUS 6666666666 ``` ## خروجی نمونه ۲ ``` 3 1234567891 FREE NO FREE BOUND 4 ``` <details class="blue"> <summary> **توضیحات نمونه ۲** </summary> در ابتدا ۲ هواپیما با آی‌دی‌های `1000000000` و `0002000000` در فرودگاه کوئرا قرار دارند. ۵ باند در این فرودگاه داریم که در ابتدا هر ۵تای آن‌ها خالی هستند. + در دستور اول هواپیمای `0002000000` قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۱ شود. (اولین باند خالی است.) + در دستور دوم هواپیمای `1234567891` قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۵ فرود بیاید. (آخرین باند خالی است) + در دستور سوم وضعیت هواپیمای `1234567891` پرسیده می‌شود. این هواپیما در وضعیت ۳ (در حال فرود آمدن) قرار دارد. پس عدد ۳ چاپ می‌شود. + در دستور چهارم وضعیت باند ۵ پرسیده می‌شود. در این باند هواپیمای `1234567891` قرار دارد و باید رشته `1234567891` چاپ شود. + در دستور پنجم هواپیمای `9876543219` قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۴ فرود بیاید. (آخرین باند خالی است) + در دستور ششم هواپیمای `5555555555` قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۳ فرود بیاید. (آخرین باند خالی است) + در دستور هفتم وضعیت باند ۲ پرسیده می‌شود. در این باند هیچ هواپیمایی وجود ندارد، پس کلمه `FREE` چاپ می‌شود. + در دستور هشتم هواپیمای `1000000000` قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۲ شود. (اولین باند خالی است.) + در دستور نهم هواپیمای `3434343434` قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است ولی هیچ باند خالی برای فرود وجود ندارد، پس عبارت `NO FREE BOUND` چاپ می‌شود. + در دستور دهم وضعیت هواپیمای `6666666666` پرسیده می‌شود. این هواپیما را تا کنون ندیده‌ایم پس در وضعیت ۴ قرار دارد. پس عدد ۴ چاپ می‌شود. </details>

فرودگاه

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

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

توضیح تصویر

این فرودگاه $k$ باند پرواز، برای بلند شدن (take-off) یا فرود آمدن (landing) هواپیماها دارد. این $k$ باند از ۱ تا $k$ شماره گذاری شده‌اند.

هر هواپیما یک رشته به طول ۱۰ و یکتا از ارقام به نام <ID> دارد که آن هواپیما را به صورت یکتا مشخص می‌کند.

در هر لحظه، هر هواپیما، یکی از چهار وضعیت زیر را دارد:

در فرودگاه کوئرا است و هیچ باندی را اشغال نکرده است.
در فرودگاه کوئرا است ولی یکی از باندها را اشغال کرده و در حال بلند شدن است.
در فرودگاه کوئرا است ولی یکی از باندها را اشغال کرده و در حال فرود آمدن است.
در فرودگاه کوئرا نیست. (یعنی این هواپیما تا کنون دیده نشده یا از همین فرودگاه به پرواز در آمده است.)

می‌دانیم در ابتدا $n$ هواپیما در فرودگاه کوئرا است (وضعیت ۱) و <ID> همه‌ی این $n$ هواپیما را داریم.

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

دستور TAKE-OFF

TAKE-OFF <ID>

این دستور یعنی هواپیمای با آی‌دی <ID> قصد بلندشدن از فرودگاه را دارد.

اگر این هواپیما در وضعیت 4 است پیام YOU ARE NOT HERE را چاپ کنید.
اگر این هواپیما در وضعیت 3 است پیام YOU ARE LANDING NOW را چاپ کنید.
اگر این هواپیما در وضعیت 2 است پیام YOU ARE TAKING OFF را چاپ کنید.
اگر این هواپیما در وضعیت 1 است ولی هیچ باند خالی نداریم پیام NO FREE BOUND را چاپ کنید.
در صورتی که هیچ کدام از اتفاقات بالا نیفتاد ابتدا وضعیت هواپیما را به 2 تغییر دهید و سپس هواپیما را به اولین (کم‌ترین شماره) باند خالی انتقال دهید تا بلند شود.

دستور LANDING

LANDING <ID>

این دستور یعنی هواپیمای با آی‌دی <ID> قصد نشستن در فرودگاه را دارد.

اگر این هواپیما در وضعیت 1 است پیام YOU ARE HERE را چاپ کنید.
اگر این هواپیما در وضعیت 2 است پیام YOU ARE TAKING OFF را چاپ کنید.
اگر این هواپیما در وضعیت 3 است پیام YOU ARE LANDING NOW را چاپ کنید.
اگر این هواپیما در وضعیت 4 است ولی هیچ باند خالی نداریم پیام NO FREE BOUND را چاپ کنید.
در صورتی که هیچ کدام از اتفاقات بالا نیفتاد ابتدا وضعیت هواپیما را به 3 تغییر دهید و سپس هواپیما را به آخرین (بزرگ‌ترین شماره) باند خالی انتقال دهید تا فرود بیاید.

دستور PLANE-STATUS

PLANE-STATUS <ID>

این دستور وضعیت هواپیمای با آی‌دی <ID> را در این لحظه درخواست می‌کند و شما باید شماره وضعیت این هواپیما را چاپ کنید.

دستور BAND-STATUS

BAND-STATUS <LINE>

این دستور وضعیت باند <LINE> را در این لحظه درخواست می‌کند و شما باید آی‌دی هواپیمایی که در این خط هست را چاپ کنید و اگر این باند آزاد است و هواپیمایی در آن نیست کلمه FREE را چاپ کنید.

ورودی🔗

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

$1 \le n, k \le 100$

در $n$ سطر بعدی در هر سطر یک رشته ۱۰ رقمی که نشان‌دهنده‌ی آی‌دی هواپیماهای داخل فرودگاه است.

در سطر بعدی عدد صحیح $q$ آمده است که نشان‌دهنده‌ی تعداد دستورات است.

$1 \le q \le 1000$

سپس در هر کدام از $q$ سطر بعدی یکی از دستورهای توضیح داده شده در کادر می‌آید.

خروجی🔗

خروجی شامل حداکثر $q$ سطر است که در سطر $i$ ام خروجی متناسب با دستورها را چاپ می‌شود.

مثال🔗

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

3 4
0000000001
0000000002
0000000003
5
TAKE-OFF 0000000001
LANDING 0000000004
PLANE-STATUS 0000000001
BAND-STATUS 4
LANDING 0000000002

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

2
0000000004
YOU ARE HERE

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

در ابتدا ۳ هواپیما با آی‌دی‌های 0000000001، 0000000002 و 0000000003 در فرودگاه کوئرا قرار دارند. ۴ باند در این فرودگاه داریم که در ابتدا هر ۴تای آن‌ها خالی هستند.

در دستور اول هواپیمای 0000000001 قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۱ شود. (اولین باند خالی است.)
در دستور دوم هواپیمای 0000000004 قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۴ فرود بیاید. (آخرین باند خالی است)
در دستور سوم وضعیت هواپیمای 0000000001 پرسیده می‌شود. این هواپیما در وضعیت ۲ (در حال بلند شدن) قرار دارد. پس عدد ۲ چاپ می‌شود.
دستور چهارم وضعیت باند ۴ پرسیده می‌شود. در این باند هواپیمای 0000000004 قرار دارد و باید رشته 0000000004 چاپ شود.
در دستور پنجم هواپیمای 0000000002 قصد فرود آمدن در فرودگاه کوئرا را دارد ولی این هواپیما اکنون در فرودگاه کوئرا است؛ پس باید پیام YOU ARE HERE چاپ شود.

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

2 5
1000000000
0002000000
10
TAKE-OFF 0002000000
LANDING 1234567891
PLANE-STATUS 1234567891
BAND-STATUS 5
LANDING 9876543219
LANDING 5555555555
BAND-STATUS 2
TAKE-OFF 1000000000
LANDING 3434343434
PLANE-STATUS 6666666666

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

3
1234567891
FREE
NO FREE BOUND
4

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

در ابتدا ۲ هواپیما با آی‌دی‌های 1000000000 و 0002000000 در فرودگاه کوئرا قرار دارند. ۵ باند در این فرودگاه داریم که در ابتدا هر ۵تای آن‌ها خالی هستند.

در دستور اول هواپیمای 0002000000 قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۱ شود. (اولین باند خالی است.)
در دستور دوم هواپیمای 1234567891 قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۵ فرود بیاید. (آخرین باند خالی است)
در دستور سوم وضعیت هواپیمای 1234567891 پرسیده می‌شود. این هواپیما در وضعیت ۳ (در حال فرود آمدن) قرار دارد. پس عدد ۳ چاپ می‌شود.
در دستور چهارم وضعیت باند ۵ پرسیده می‌شود. در این باند هواپیمای 1234567891 قرار دارد و باید رشته 1234567891 چاپ شود.
در دستور پنجم هواپیمای 9876543219 قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۴ فرود بیاید. (آخرین باند خالی است)
در دستور ششم هواپیمای 5555555555 قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است و می‌تواند در باند ۳ فرود بیاید. (آخرین باند خالی است)
در دستور هفتم وضعیت باند ۲ پرسیده می‌شود. در این باند هیچ هواپیمایی وجود ندارد، پس کلمه FREE چاپ می‌شود.
در دستور هشتم هواپیمای 1000000000 قصد بلند شدن دارد. با توجه به اینکه در این لحظه در فرودگاه کوئرا است و در وضعیت ۱ قرار دارد، می‌تواند وارد باند ۲ شود. (اولین باند خالی است.)
در دستور نهم هواپیمای 3434343434 قصد فرود در فرودگاه کوئرا را دارد. باتوجه به اینکه این هواپیما را تاکنون ندیده‌ایم پس در فرودگاه کوئرا اکنون حضور ندارد و روی هوا است ولی هیچ باند خالی برای فرود وجود ندارد، پس عبارت NO FREE BOUND چاپ می‌شود.
در دستور دهم وضعیت هواپیمای 6666666666 پرسیده می‌شود. این هواپیما را تا کنون ندیده‌ایم پس در وضعیت ۴ قرار دارد. پس عدد ۴ چاپ می‌شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک دنباله از اعداد صحیح و مثبت مثل $a_1, a_2, \dots, a_n \,$ داریم. $q$ درخواست داریم که باید آن‌ها را به‌ترتیب انجام دهیم: ### درخواست نوع اول $$+ \,\, idx \,\, val$$ در این در‌خواست از شما می‌خواهیم مقدار $a_{idx}$ را به $val$ تغییر بده. ### درخواست نوع دوم $$? \,\, l \,\, r$$ در این درخواست از شما می‌خواهیم بررسی کنید آیا بازه $a_l, \dots, a_r$ تشکیل یک جایگشت از اعداد $1$ تا $r - l + 1$ می‌دهد یا خیر. # ورودی در سطر اول ورودی، دو عدد صحیح و مثبت $n$ و $q$ با یک فاصله از هم جدا‌شده‌اند، آمده است. $$1 \leq n, q \leq 100 \ 000$$ در سطر دوم، $n$ عدد صحیح و مثبت که نشان دهنده‌ی مقدارهای $a_1, a_2, \dots, a_n \,$ است. $$1 \leq a_i \leq n$$ در $q$ سطر بعدی، در هر سطر، یکی از دو نوع دستور گفته شده در سوال می‌آید. اگر درخواست از نوع اول باشد، در یک سطر ابتدا کاراکتر `+` می‌آید، سپس با یک فاصله دو عدد صحیح $idx$ و $val$ داده می‌شود. $$1 \leq idx, val \leq n$$ اگر درخواست از نوع دوم باشد، در یک سطر ابتدا کاراکتر `?` می‌آید، سپس با یک فاصله دو عدد صحیح $l$ و $r$ داده می‌شود. $$1 \leq l \leq r \leq n$$ # خروجی تعداد سطرهای خروجی، به تعداد درخواست‌های نوع دوم است. در صورت تشکیل جایگشت در بازه آن درخواست، عبارت `YES` و در صورت جایگشت نبودن آن، عبارت`NO` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 6 1 3 2 ? 1 2 ? 1 3 + 2 2 ? 1 2 + 3 1 ? 2 3 ``` ## خروجی نمونه ۱ ``` NO YES YES YES ``` ## ورودی نمونه ۲ ``` 5 5 1 2 1 2 1 ? 3 5 + 3 3 ? 1 3 ? 3 5 ? 2 4 ``` ## خروجی نمونه ۲ ``` NO YES YES NO ```

جایگشت بودن

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

یک دنباله از اعداد صحیح و مثبت مثل $a_1, a_2, \dots, a_n \,$ داریم. $q$ درخواست داریم که باید آن‌ها را به‌ترتیب انجام دهیم:

درخواست نوع اول🔗

$+ \,\, idx \,\, val$

در این در‌خواست از شما می‌خواهیم مقدار $a_{idx}$ را به $val$ تغییر بده.

درخواست نوع دوم🔗

$? \,\, l \,\, r$

در این درخواست از شما می‌خواهیم بررسی کنید آیا بازه $a_l, \dots, a_r$ تشکیل یک جایگشت از اعداد $1$ تا $r - l + 1$ می‌دهد یا خیر.

ورودی🔗

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

در سطر دوم، $n$ عدد صحیح و مثبت که نشان دهنده‌ی مقدارهای $a_1, a_2, \dots, a_n \,$ است. $1 \leq a_i \leq n$

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

اگر درخواست از نوع اول باشد، در یک سطر ابتدا کاراکتر + می‌آید، سپس با یک فاصله دو عدد صحیح $idx$ و $val$ داده می‌شود.

$1 \leq idx, val \leq n$

اگر درخواست از نوع دوم باشد، در یک سطر ابتدا کاراکتر ? می‌آید، سپس با یک فاصله دو عدد صحیح $l$ و $r$ داده می‌شود.

$1 \leq l \leq r \leq n$

خروجی🔗

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

مثال🔗

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

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

NO
YES
YES
YES

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

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

NO
YES
YES
NO

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- سورنا برای کسب درآمد به کشوری سفر می‌کند که $n + 1$ جزیره دارد و جزیره‌های آن به ترتیب با اعداد $0$ تا $n$ شماره گذاری شده‌اند. او با خودش تمام زیرمجموعه‌های اعداد ۱ تا $n$ را برده است تا بفروشد! ![توضیح تصویر](https://quera.org/qbox/view/YMm57wLucL/F-1.png) سفر سورنا از جزیره‌ی $0$ آغاز می‌شود و هر بار از جزیره‌ی شماره $k$، به جزیره‌ی $k + 1$ می‌رود. (او نمی‌خواهد این ترتیب را تغییر دهد.) اهالی جزیره‌ی شماره $k$، حاضرند همه زیرمجموعه‌های $k$ عضوی او را بخرند و به ازای هر زیرمجموعه، یک سکه طلا به سورنا بدهند. تجارت پر سودی است اما مشکل اینجاست که ارزش ۱ سکه طلا $2^n$ ریال است و زمانی که سورنا از یک جزیره به جزیره‌ی بعدی می‌رود، قیمت یک سکه طلا نصف می‌شود. توجه کنید سورنا نمی‌تواند همان لحظه بعد از معامله سکه را به پول نقد تبدیل کند و باید وقتی به کشورش برگشت سکه‌ها را تبدیل کند. از شما می‌خواهیم کوچک‌ترین $k$ را پیدا کنید که اگر سورنا سفرش را در جزیره $k$ام پایان دهد، سود او بیشینه می‌شود. # ورودی ورودی $t$ تست‌کیس دارد. $$1 \leq t \leq 100$$ برای هر تست، در یک سطر ورودی عدد صحیح و مثبت $n$ آمده است. $$2 \leq n \leq 10^{18}$$ # خروجی برای هر تست، در یک سطر، کوچک‌ترین $k$‌ای را چاپ کنید که اگر سورنا سفرش را در این جزیره پایان دهد، سود او بیشینه می‌شود. # مثال ## ورودی نمونه ۱ ``` 3 2 12 5 ``` ## خروجی نمونه ۱ ``` 1 4 2 ``` توضیح تست‌کیس سوم: این کشور ۶ جزیره با شماره‌های ۰ تا ۵ دارد. سورنا با خودش همه زیرمجموعه‌های مجموعه‌ی $\{1, 2, \dots, 5\}$ را می‌برد. همانطور که می‌دانید این مجموعه: + ۱ زیرمجموعه‌ی ۰ عضوی + ۵ زیرمجموعه‌ی ۱ عضوی + ۱۰ زیرمجموعه‌ی ۲ عضوی + ۱۰ زیرمجموعه‌ی ۳ عضوی + ۵ زیرمجموعه‌ی ۴ عضوی + ۱ زیرمجموعه‌ی ۵ عضوی دارد. همچنین قیمت یک سکه طلا، ۳۲ ریال است. + اگر سورنا بخواهد در **جزیره‌ی ۰** به سفرش پایان دهد تنها زیرمجموعه تهی را می‌تواند بفروشد و ۱ سکه طلا بدست می‌آورد. باتوجه به اینکه هنوز سفر بین جزیره‌ای انجام نشده، قیمت سکه ۳۲ ریال است. پس می‌تواند در مجموع **۳۲ ریال** سود کند. + اگر سورنا بخواهد در **جزیره‌ی ۱** به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰ و پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ بفروشد. پس می‌تواند ۶ سکه طلا بدست بیاورد. باتوجه به اینکه یک سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱۶ ریال است. پس می‌تواند در مجموع **۹۶ ریال** سود کند. + اگر سورنا بخواهد در **جزیره‌ی ۲** به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ و ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ بفروشد. پس می‌تواند ۱۶ سکه طلا بدست بیاورد. باتوجه به اینکه دو سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۸ ریال است. پس می‌تواند در مجموع **۱۲۸ ریال** سود کند. + اگر سورنا بخواهد در **جزیره‌ی ۳** به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ و ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ بفروشد. پس می‌تواند ۲۶ سکه طلا بدست بیاورد. باتوجه به اینکه سه سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۴ ریال است. پس می‌تواند در مجموع **۱۰۴ ریال** سود کند. + اگر سورنا بخواهد در **جزیره‌ی ۴** به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ و پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ بفروشد. پس می‌تواند ۳۱ سکه طلا بدست بیاورد. باتوجه به اینکه چهار سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۲ ریال است. پس می‌تواند در مجموع **۶۲ ریال** سود کند. + اگر سورنا بخواهد در **جزیره‌ی ۵** به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳، پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ و یک زیرمجموعه‌ی پنج عضوی را در جزیره‌ی شماره ۵ بفروشد. پس می‌تواند ۳۲ سکه طلا بدست بیاورد. باتوجه به اینکه پنج سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱ ریال است. پس می‌تواند در مجموع **۳۲ ریال** سود کند. بنابراین بیشترین سودی که می‌تواند بکند زمانی است که در جزیره‌ی شماره ۲ به سفرش پایان دهد.

مسیر تورمی

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

سورنا برای کسب درآمد به کشوری سفر می‌کند که $n + 1$ جزیره دارد و جزیره‌های آن به ترتیب با اعداد $0$ تا $n$ شماره گذاری شده‌اند. او با خودش تمام زیرمجموعه‌های اعداد ۱ تا $n$ را برده است تا بفروشد!

توضیح تصویر

سفر سورنا از جزیره‌ی $0$ آغاز می‌شود و هر بار از جزیره‌ی شماره $k$ ، به جزیره‌ی $k + 1$ می‌رود. (او نمی‌خواهد این ترتیب را تغییر دهد.)

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

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

توجه کنید سورنا نمی‌تواند همان لحظه بعد از معامله سکه را به پول نقد تبدیل کند و باید وقتی به کشورش برگشت سکه‌ها را تبدیل کند.

از شما می‌خواهیم کوچک‌ترین $k$ را پیدا کنید که اگر سورنا سفرش را در جزیره $k$ ام پایان دهد، سود او بیشینه می‌شود.

ورودی🔗

ورودی $t$ تست‌کیس دارد. $1 \leq t \leq 100$

برای هر تست، در یک سطر ورودی عدد صحیح و مثبت $n$ آمده است.

$2 \leq n \leq 10^{18}$

خروجی🔗

برای هر تست، در یک سطر، کوچک‌ترین $k$ ‌ای را چاپ کنید که اگر سورنا سفرش را در این جزیره پایان دهد، سود او بیشینه می‌شود.

مثال🔗

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

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

1
4
2

توضیح تست‌کیس سوم:

این کشور ۶ جزیره با شماره‌های ۰ تا ۵ دارد.

سورنا با خودش همه زیرمجموعه‌های مجموعه‌ی $\{1, 2, \dots, 5\}$ را می‌برد. همانطور که می‌دانید این مجموعه:

۱ زیرمجموعه‌ی ۰ عضوی
۵ زیرمجموعه‌ی ۱ عضوی
۱۰ زیرمجموعه‌ی ۲ عضوی
۱۰ زیرمجموعه‌ی ۳ عضوی
۵ زیرمجموعه‌ی ۴ عضوی
۱ زیرمجموعه‌ی ۵ عضوی دارد.

همچنین قیمت یک سکه طلا، ۳۲ ریال است.

اگر سورنا بخواهد در جزیره‌ی ۰ به سفرش پایان دهد تنها زیرمجموعه تهی را می‌تواند بفروشد و ۱ سکه طلا بدست می‌آورد. باتوجه به اینکه هنوز سفر بین جزیره‌ای انجام نشده، قیمت سکه ۳۲ ریال است. پس می‌تواند در مجموع ۳۲ ریال سود کند.
اگر سورنا بخواهد در جزیره‌ی ۱ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰ و پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ بفروشد. پس می‌تواند ۶ سکه طلا بدست بیاورد. باتوجه به اینکه یک سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱۶ ریال است. پس می‌تواند در مجموع ۹۶ ریال سود کند.
اگر سورنا بخواهد در جزیره‌ی ۲ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱ و ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ بفروشد. پس می‌تواند ۱۶ سکه طلا بدست بیاورد. باتوجه به اینکه دو سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۸ ریال است. پس می‌تواند در مجموع ۱۲۸ ریال سود کند.
اگر سورنا بخواهد در جزیره‌ی ۳ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲ و ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ بفروشد. پس می‌تواند ۲۶ سکه طلا بدست بیاورد. باتوجه به اینکه سه سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۴ ریال است. پس می‌تواند در مجموع ۱۰۴ ریال سود کند.
اگر سورنا بخواهد در جزیره‌ی ۴ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳ و پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ بفروشد. پس می‌تواند ۳۱ سکه طلا بدست بیاورد. باتوجه به اینکه چهار سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۲ ریال است. پس می‌تواند در مجموع ۶۲ ریال سود کند.
اگر سورنا بخواهد در جزیره‌ی ۵ به سفرش پایان دهد، می‌تواند یک زیرمجموعه تهی را در جزیره‌ی شماره ۰، پنج زیرمجموعه‌ی یک عضوی را در جزیره‌ی شماره ۱، ده زیرمجموعه‌ی دو عضوی را در جزیره‌ی شماره ۲، ده زیرمجموعه‌ی سه عضوی را در جزیره‌ی ۳، پنج زیرمجموعه‌ی چهار عضوی را در جزیره‌ی ۴ و یک زیرمجموعه‌ی پنج عضوی را در جزیره‌ی شماره ۵ بفروشد. پس می‌تواند ۳۲ سکه طلا بدست بیاورد. باتوجه به اینکه پنج سفر بین جزیره‌ای انجام شده‌است، قیمت سکه ۱ ریال است. پس می‌تواند در مجموع ۳۲ ریال سود کند.

بنابراین بیشترین سودی که می‌تواند بکند زمانی است که در جزیره‌ی شماره ۲ به سفرش پایان دهد.