+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دریا امروز آرام است. بنابراین آقای اسپارو و دوستش تصمیم گرفته‌اند در هوای خوب عرشه *هفت سنگ* بازی کنند. برای این امر آن‌ها ۷ سنگ با شماره‌های ۱ تا ۷ را به ترتیبی روی هم چیده‌اند. سپس آقای اسپارو به یکی سنگ‌ها ضربه می‌زند. در اثر ضربه‌ی آقای اسپارو، همه‌ی سنگ‌هایی که بالای سنگ ضربه خورده بودند روی زمین می‌افتند. همچنین خود سنگ مورد ضربه نیز در صورتی که از قبل روی زمین نبوده باشد روی زمین می‌افتد. دوست آقای اسپارو که در ضربه زدن مهارتی ندارد، تصمیم گرفته محاسبه کند که اگر آقای اسپارو به سنگ با شماره‌ی $x$ ضربه بزند، چند سنگ روی زمین می‌افتند. به او در پیدا کردن این مقدار کمک کنید. # ورودی در خط اول ورودی، ۷ عدد $p_1, p_2, \dots, p_7\,$ به ترتیب از چپ به راست آمده‌اند (چپ‌ترین عدد $p_1$ و راست‌ترین عدد $p_7$ است) که نشان‌دهنده‌ی ترتیب قرار گیری سنگ‌ها روی زمین هستند. سنگ با شماره‌ی $p_1$ پایین‌ترین سنگ و سنگ با شماره‌ی $p_7$ بالاترین سنگ است. تضمین می‌شود $p_1, p_2, \dots, p_7\,$ یک جایگشت از اعداد ۱ تا ۷ است. در خط بعدی ورودی عدد $1 \le x \le 7$ آمده است که نشان دهنده‌ی شماره‌ی سنگی است که آقای اسپارو به آن ضربه زده. # خروجی در تنها خط خروجی، تعداد سنگ‌هایی که پس از ضربه‌ی آقای اسپارو روی زمین می‌افتند را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 6 1 7 2 4 3 5 2 ``` ## خروجی نمونه ۱ ``` 4 ``` پس از ضربه‌ی آقای اسپارو به سنگ با شماره‌ی ۲، سنگ‌های با شماره‌های ۲، ۴، ۳ و ۵ روی زمین می‌افتند. ## ورودی نمونه ۲ ``` 6 2 7 1 3 4 5 6 ``` ## خروجی نمونه ۲ ``` 6 ``` پس از ضربه‌ی آقای اسپارو به سنگ با شماره‌ی ۶ که پایین‌ترین سنگ است، همه‌ی سنگ‌ها به جز خود سنگ ۶ که از قبل روی زمین بوده، روی زمین می‌افتند. **نکته:** در صورتی که از زبان جاوااسکریپت برای حل سوال استفاده می‌کنید، حتما *Javascript* را به عنوان زبان انتخاب کرده و از تابع `readline` برای خواندن ورودی‌ها استفاده کنید. برای اطلاع بیشتر می‌توانید [این لینک](https://quera.org/course/assignments/2693/problems/8774) را ببینید.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- به تازگی یک بحث داغ در یک گروه بزرگ در **بله** شکل گرفته‌است. البته بیشتر افراد گروه فقط تماشاگر هستند و تنها ۴ شخصیت زیر که معرفی می‌کنیم پیام می‌دهند. ‌ 1. پیگیر: او کسی است که **پیام اول** را می‌دهد و بعد از **هر $t$ پیام** که **دیگران** دهند، او دوباره بلافاصله پیام می‌دهد (در واقع پیگیری می‌کند). 2. طناز: او **پیام دوم** را می‌دهد و بعد از هر پیام **مرشد** باز پیام می‌دهد (در واقع مسخره‌بازی می‌کند و جوک می‌گوید و...). 3. جدی: او بعد از هر پیام **طناز** پیام می‌دهد (در واقع از طناز می‌خواهد که در بحث به این مهمی جدی باشد). 4. مرشد: او بعد از هر پیام **جدی** پیام می‌دهد (در واقع آداب بحث و رعایت ادب را متذکر اعضا می‌شود). توجه کنید چنان‌چه دو نفر بخواهند با هم پیام دهند به ترتیب اولویت نوشته‌شده پیام آن‌ها ارسال می‌شود. به طور خاص پیام پیگیر بالاترین اولیت را دارد. حال اعضای گروه از شما در تعدادی پرسش می‌خواند مشخص کنید که پیام شماره $k$ را چه کسی ارسال خواهد کرد. # ورودی در سطر اول دو عدد $q$ تعداد پرسش‌ها و $t$ میزان پیگیری پیگیر می‌آید. سپس در سطر $i$ از $q$ سطر بعد عدد $k_i$ پرسش تماشاگران می‌آید. $$1 \le t, q \le 100 \, 000$$ $$1 \le k_i \le 10^{9} \quad (1 \le i \le q)$$ # خروجی در سطر $i$ از $q$ سطر خروجی نام کسی که پیام $k_i$ داده‌است را خروجی دهید. به بزرگی و کوچکی حروف توجه کنید و نام‌های خروجی باید یک از ۴ حالت `Peygir`, `Tannaz`, `Jeddy`, `Morshed` باشند. # مثال ## ورودی نمونه ۱ ``` 6 3 1 2 3 4 5 6 ``` ## خروجی نمونه ۱ ``` Peygir Tannaz Jeddy Morshed Peygir Tannaz ``` 1. در پیام اول، پیگیر پیامش را ارسال می‌کند. 2. سپس در پیام دوم طناز پیامی ارسال می‌کند. 3. پس از آن در پیام سوم جدی در پاسخ به پیامی که طناز در ثانیه‌ی دوم ارسال کرده پیامش را ارسال می‌کند. 4. بعد از آن در پیام چهارم مرشد در پاسخ به پیام ثانیه‌ی سوم جدی پیامش را ارسال می‌کند. 5. بعد از این مراحل در پیام پنجم، از آن‌جایی که ۳ پیام پس از آخرین پیام پیگیر ارسال شده، پیگیر مجددا پیامش را ارسال می‌کند. توجه کنید که در این لحظه طناز هم قصد ارسال پیام داشته. اما از آن‌جایی که اولویت ارسال پیام با پیگیر است، پیام پیگیر ابتدا فرستاده می‌شود. 6. پس از آن در پیام ششم، طناز در پاسخ به پیام چهارم که مرشد فرستاده بود، پیام خود را می‌فرستد. ## ورودی نمونه ۲ ``` 8 9 1 2 3 4 5 68617368 229436468 791709 ``` ## خروجی نمونه ۲ ``` Peygir Tannaz Jeddy Morshed Tannaz Tannaz Tannaz Jeddy ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شرکت تخریب‌گران محیط زیست مسئول هموار کردن شهرها جهت سهولت در حمل و نقل شده. بدین منظور آن‌ها می‌خواهند در **همه** کوه‌های شهر تونل حفر کنند تا شهر **هموار** شود. به طور دقیق‌تر می‌توان شهر را به صورت یک جدول با **میلیارد** سطر و ستون نشان داد که در برخی از خانه‌های آن کوه واقع شده است. این شرکت به تازگی یک بولدوزر قوی خریده است. بولدوزر می‌تواند در یک حرکت **سطری** در تمام کوه‌های یک سطر تونل بکند، به طور مشابه در یک حرکت **ستونی** می‌تواند در تمام کوه‌های یک ستون تونل حفر کند. به این شرکت کمک کنید که آیا هر شهر را با دقیقا **یک** حرکت سطری و **یک** حرکت ستونی بولدوزر می‌توان هموار کرد؟ # ورودی در خط اول ورودی $t$ تعداد شهرهای مورد برسی می‌آید سپس اطلاعات $t$ شهر در خطوط بعد به ترتیب جداگانه می‌آید. در خط اول اطلاعات شهر $i$، $m_i$ تعداد کوه‌های شهر می‌آید و سپس در خط $j$ از $m_i$ خط بعد دو عدد $x_{ij}$ شماره سطر کوه $j$ و $y_{ij}$ شماره ستون آن می‌آید. تضمین می‌شود کوه‌های یک شهر در نقاط متمایز داده‌شوند. $$t \le 12 \, 000$$ $$\sum_{i=1}^t m_i \le 300 \, 000$$ $$1 \le x_{ij}, y_{ij} \le 10^9$$ # خروجی برای هر شهر به ترتیب اگر با دقیقا یک حرکت سطری و یک حرکت ستونی هموارشدنی بود ‍‍ ‍‍‍`YES` وگرنه `NO` را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 4 3 1 1 1 2 1 3 5 1 1 1 3 2 2 3 1 3 3 4 1 4 2 4 3 4 4 4 4 1 2 2 1 2 3 3 2 ``` ## خروجی نمونه ۱ ``` YES NO YES YES ``` در شهر اول، کافی است کوه‌های سطر اول و ستون حفر شوند. می‌توان نشان داد که در شهر دوم عملیات مورد نیاز شرکت ممکن نیست. در شهر سوم، شرکت می‌تواند کوه‌های سطر سوم و ستون چهارم را حفر کند. نهایتا در شهر چهارم، تخریب‌گران می‌توانند کوه‌های سطر و ستون دوم را حفر کنند تا به هدف خود برسند.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- ۴ دزد دریایی قصد دارند گنج‌هایی که اخیرا در دریا پیدا کرده‌اند را بین یک‌دیگر تقسیم کنند. دریا به صورت جدولی $n$ در $m$ است و دزدها $k$ گنج در آن پیدا کرده‌اند. گنج $i$-ام در خانه‌ی واقع در سطر $x_i$-ام و ستون $y_i$-ام جدول قرار دارد. از آن‌جایی که دزدها انسان‌های منصفی هستند تقسیم‌بندی باید به گونه‌ای صورت گیرد که دزدها سهم یکسانی از گنج‌ها داشته باشند. برای این منظور دزدها باید یک خط افقی و یک خط عمودی *از خطوط جدول* انتخاب کنند و با استفاده از این خطوط جدول را به ۴ بخش تقسیم کنند. این خطوط باید به گونه‌ای انتخاب شوند که تعداد گنج‌های واقع شده در قسمت‌های به وجود آمده با هم برابر باشند. دریا اخیرا مواج بوده و دزدهای دریایی حال مساعدی ندارند. بنابراین از شما می‌خواهند که با گرفتن اطلاعات دریا و گنج‌ها به آن‌ها بگویید که چنین تقسیم‌بندی‌ای وجود دارد یا خیر. # ورودی در خط اول ورودی عدد $1 \le t \le 1000$ که نشان‌دهنده‌ی تعداد سناریوهاست آمده است. در خط اول هر سناریو، اعداد $2 \le n,m \le 10^9$ و $1 \le k \le 100\,000$ که نشان‌دهنده‌ی ابعاد دریا و تعداد گنج‌ها هستند آمده‌اند. سپس در هر یک از $k$ خط بعدی سناریو، دو عدد $1 \le x_i \le n$ و $1 \le y_i \le m$ که نشان‌دهنده‌ی مختصات قرارگیری گنج $i$-ام هستند آمده‌اند. تضمین می‌شود مجموع مقادیر $k$ در همه‌ی سناریوها حداکثر برابر $100\,000$ است. # خروجی برای هر سناریو، در صورتی که روش معتبری برای تقسیم‌بندی وجود دارد عبارت `YES` و در غیر این صورت عبارت `NO` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 2 3 4 1 1 1 3 2 1 2 3 2 2 4 1 1 1 1 2 2 2 2 3 3 4 1 2 2 1 2 3 3 2 1000000000 1000000000 1 6 8 ``` ## خروجی نمونه ۱ ``` YES NO NO NO ``` در سناریوی اول، دزدهای دریایی می‌توانند دریا را با خط افقی بین سطر اول و دوم و خط عمودی بین ستون دوم و سوم تقسیم کنند. در این صورت در هر یک از قسمت‌های به وجود آمده دقیقا ۱ گنج قرار خواهد گرفت.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- فربد برای تنوع ذهنی مدتی است برنامه‌نویسی الگوریتمی را کنار گذاشته و به باغبانی روی آورده. حال فصل زمستان از راه رسیده و او می‌خواهد درخت‌های خود را هرس کند. از آنجا که تفکر الگوریتمی در تمام زندگی یار اوست او می‌خواهد هرس را طوری انجام دهد که **آویزانی ریشه کمینه می‌شود.** به عبارت دیگر [درخت‌های ریشه‌دار](https://fa.wikipedia.org/wiki/%D8%AF%D8%B1%D8%AE%D8%AA) او شبیه [درخت‌های ریشه‌دار](https://gtoi.shaazzz.ir/book/2/1.html) می‌مانند. یعنی می‌توان آنها را با گرافی $n$ راسی، همبند و بدون دور مدل کرد و **راس شماره یک** را به عنوان ریشه در نظر گرفت. میزانه آویزانی یک برگ برابر ۱ است و آویزانی رئوس دیگر برابر یک به‌علاوه بیشینه آویزانی بچه‌های آن تعریف می‌شود. همانطور که گفته‌شد او نمی‌خواهد دست به کد شود پس به او کمک کنید. **توجه کنید که او چون درخت خود را دوست دارد نمی‌خواهد بیشتر از $k$ بار آن را هرس کند و در هر عملیات هرس او دقیقا یک برگ درخت به همراه یال متصل به آن را حذف می‌کند. همچنین راسی ممکن است در ابتدا برگ نباشد و پس از تعدادی هرس به برگ تبدیل شود و نیز ریشه درخت هرس نشدنی است.** # ورودی در سطر اول ورودی $t$ به عنوان تعداد درخت‌های فربد می‌آید. سپس اطلاعات $t$ درخت به شرح زیر می‌آید. در سطر اول اطلاعات درخت $r$ عدد $n_r$ تعداد رئوس درخت و $k_r$ حداکثر تعداد هرس‌های مجاز می‌آید. سپس در سطر $i$ از $n-1$ سطر بعد در هر سطر دو عدد $u_{ri}$ و $v_{ri}$ می‌آید که نشان‌دهنده وجود یک یال بین آن دو راس است. تضمین می‌شود گراف ورودی درخت است. $$t \le 10 \, 000$$ $$1 \le n_i, \sum_{r=1}^t n_r \le 500 \, 000 \quad (1 \le i \le t)$$ $$0 \le k_r \le n_r-1 \quad (1 \le r \le t)$$ $$1 \le u_{ri}, v_{ri} \le n_r$$ # خروجی به ازای هر درخت کمینه آویزانی ریشه پس از هرس کردن حداکثر $k$ برگ را در خطوط متفاوت خروجی دهید. # مثال ## ورودی نمونه ۱ ``` 2 3 2 1 2 1 3 6 1 1 2 1 3 3 4 3 5 4 6 ``` ## خروجی نمونه ۱ ``` 1 3 ``` در درخت اول، فربد می‌تواند رأس‌های با شماره‌های ۲ و ۳ را هرس کند. پس از این کار تنها رأس باقی‌مانده رأس شماره‌ی ۱ خواهد بود که از آن‌جایی که هیچ فرزندی ندارد برگ حساب می‌شود و آویزانی آن برابر ۱ خواهد بود. در درخت دوم، فربد رأس شماره‌ی ۶ را حذف می‌کند و بدین‌ترتیب آویزانی درخت برابر ۳ خواهد شد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- نَقلی خیالی موجود است که مرحوم تورینگ فردی شکّاک و کم حافظه بود. او برای اینکه ماشین دلبندش دست نااهلان نیفتد رمزی عددی برای آن تعریف کرد. رمز عددی با ارقام کافی رمز مطمئنی بود چرا که ماشین دیگری نبود که بخواهد رمز را بشکند. از آنجا که وی نمی‌توانست رمز خود را حفظ کند تصمیم گرفت رمز خود را بر روی کاغذی یادداشت کند. از آنجا که کاغذ نیز ممکن بود دست نااهلان بیفتد او رمز را به صورت یک **رشته منطقی** روی کاغذ نوشت. از بد ماجرا گویا وی **دقیقا یک قسمت** از رشته منظقی را اشتباه یادداشت کرده‌بود و دیگر نمی‌توانست رمز خود را بازیابی کند. او همه بخش‌های رشته که به آن شک داشت را در وصیت‌نامه خود نوشت تا بلکه کسی رمز اصلی را بازیابد. رمزهای ممکن برای ماشین تورینگ را بازیابی کنید. توجه کنید شک‌های تورینگ از دو نوع زیر هستند: 1. او شک می‌کند که ادات $i$ـم رشته (از چپ) شاید $o$ بوده‌باشد. 2. او شک می‌کند که عدد $i$ـم رشته (از چپ) شاید $x$ بوده‌باشد. برای درک بهتر به مثال‌ها و توضیحات آنها توجه کنید. منظور از **رشته منطقی** یک رشته است که از [ادات‌های دودویی](https://fa.wikipedia.org/wiki/%D8%B9%D9%85%D9%84%DB%8C%D8%A7%D8%AA_%D8%A8%DB%8C%D8%AA%DB%8C) and, or و xor به ترتیب با نمادهای &, | و ^ به همراه **اعداد صحیح نامنفی** و **پرانتزگذاری کامل و معتبر** تشکیل شده‌است. منظور از **پرانتزگذاری کامل** این است که متناظر **هر ادات دقیقا یک پرانتز باز و یک پرانتز بسته** وجود دارد و این باعث عدم ابهام در اولویت عملگرها می‌شود. # ورودی در سطر اول ورودی $s$ یا همان رشته منطقی ابتدایی تورینگ می‌آید. همچنین در سطر بعد عدد $q$ تعداد شک‌های تورینگ می‌آید. سپس سطر $i$ـم از $q$ سطر بعد به یکی از دو شکل `1 k o` و `2 k x` است. که در شکل اول تورینگ شک می‌کند که شاید ادات $k$ـم رشته $o$ باشد که می‌دانیم $o$ یکی از & نماد and و | نماد or ویا ^ نماد xor است. در شکل دوم نیز تورینگ شک می کند که $k$ـمین عدد ظاهر شده در رشته شاید $x$ بوده باشد. توجه کنید که شک وی به ادات و عددی است که وجود دارد و به چیزی که وجود ندارد شک نمی‌کند ولی ممکن است رشته پس از شک او با رشته اولیه یکی باشد(مانند شک اول نمونه ۲). $$5 \le |s| \le 300 \, 000$$ $$1 \le q \le 300 \, 000$$ همچنین تضمین می‌شود تمام اعداد رشته ابتدایی و شک تورینگ **اعداد صحیح نامنفی و حداکثر میلیارد** باشند. # خروجی در سطر $i$ـم از $q$ سطر ارزش رشته منطقی حاصل از جایگذاری شک $i$ـم را خروجی دهید. توجه کنید شک‌ها تاثیری بر رشته ابتدایی نمی‌گذارند و از هم مستقل‌اند. # مثال ## ورودی نمونه ۱ ``` (5|1) 5 1 1 & 1 1 | 1 1 ^ 2 1 2 2 2 6 ``` ## خروجی نمونه ۱ ``` 1 5 4 3 7 ``` در شک اول، رشته برابر (1&5) است که مقدار آن برابر $1$ است. در شک دوم، رشته برابر $(5|1)$ است که مقدار آن برابر $5$ است. در شک سوم، رشته برابر (1^5) است که مقدار آن برابر $4$ است. در شک چهارم، رشته برابر $(2|1)$ است که مقدار آن برابر $3$ است. در شک پنجم، رشته برابر $(5|6)$ است که مقدار آن برابر $7$ است. ## ورودی نمونه ۲ ``` ((10&10)|(7^6)) 10 2 1 10 2 2 256 1 1 ^ 1 2 & 1 2 ^ 1 3 & 1 3 | 2 3 6 2 4 7 2 3 16 ``` ## خروجی نمونه ۲ ``` 11 1 1 0 11 14 15 10 10 30 ```