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

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

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

• حداقل سه مورد قرمز باشند.
• حداقل دو مورد قرمز و حداقل دو مورد زرد باشند.
• همه موارد زرد یا قرمز باشند.

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

ورودی🔗

ورودی تنها شامل یک سطر است که در آن برچسب سلامت به صورت یک رشته متشکل از پنج حرف آمده‌است؛ R نشان‌دهنده‌ی رنگ قرمز، Y نشان‌دهنده‌ی رنگ زرد، و G نشان‌دهنده‌ی رنگ سبز است.

خروجی🔗

در صورتی که برچسب ورودی یک برچسب خطرناک باشد در تنها سطر خروجی عبارت nakhor lite را چاپ کنید و در غیر این صورت عبارت rahat baash را چاپ کنید.

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

GGGGG

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

rahat baash

در نمونه‌ی بالا، همه‌ی موارد سبز هستند و خوردن این خوراکی هیچ خطری ندارد.

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

RYRYR

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

nakhor lite

خوراکی بالا هر سه شرط گفته شده را دارد که حتی با داشتن یکی از آن‌ها خطرناک میشد؛ پس خیلی خطرناک است!

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

بعد از مدت‌ها که لیته توانست با موفقیت چالش خوش‌اندام شدن را تا حدودی پشت سر بگذارد، فیته نیز کم‌کم به او علاقه‌مند شد و امروز آن‌ها می‌خواهند به اولین قرار خود بروند. لیته در نقطه $a$ شهر زندگی می‌کند و فیته نقطه $b$ را برای اولین قرار انتخاب کرده‌است.

در این شهر دو نوع قطار برای جا‌به‌جایی وجود دارد:

• نوع اول: نقطه $x$ و $x + 1$ را با یک مسیر دو طرفه به هم متصل می‌کند. ( به ازای هر $x$ صحیح )
• نوع دوم: نقطه $k \times x$ و $k \times (x +1)$ را با یک مسیر دوطرفه به هم متصل می‌کند. ( به ازای هر $x$ صحیح و $k$ داده شده در ورودی )

هم چنین می‌دانیم فاصله طی کردن یک مسیر بین دو نقطه به ازای هر‌نوع قطار دقیقا یک دقیقه است.

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

ورودی🔗

ورودی تنها شامل یک سطر است که در آن به ترتیب سه عدد صحیح $k$ و $a$ و $b$ با فاصله از هم آمده‌است. $-10^9 \le a, b \le 10^9$ $1 \le k \le 10^9$

خروجی🔗

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

ورودی نمونه🔗

4 1 10

خروجی نمونه🔗

5

نمونه‌ی بالا همان تصویر موجود در صورت سوال است؛ مسیر بهینه با ۵ سفر در تصویر پررنگ شده است.

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

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

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

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

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

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

ورودی🔗

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

در هر کدام از $n$ سطر بعد اطلاعات نفر $i$-اُم که به لیته پیام می‌دهد، آمده‌است. این سطر شامل دو عدد صحیح $l$ و $r$ است و یعنی نفر $i$-اُم در دقیقه $l$ به لیته پیام‌ می‌دهد و حداکثر تا دقیقه $r$ منتظر جواب لیته می‌ماند.

• به ازای نفر $i$-اُم لیته می‌تواند از دقیقه $l$ تا دقیقه $r$ (شامل هر دو) به او جواب بدهد.

$1 \le k \le n \le 100\ 000$ $1 \le l \le r \le 100\ 000$

خروجی🔗

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

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

3 2
1 2
1 100
1 1

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

YES

توضیحات: لیته در زمان ۱ مجبور است جواب نفر سوم را بدهد. در همان زمان(زمان ۱) جواب نفر دوم را هم می‌دهد. سپس در زمان ۲، جواب نفر اوّل را هم می‌دهد.

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

3 2
3 3
3 3
3 3

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

NO

توضیحات: لیته مجبور است در زمان ۳ جواب هر ۳ نفر را بدهد. ولی ظرفیت لیته ۲ نفر است. پس جواب این تست NO خواهد بود.

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

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

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

دیجیکالا $n$ نوع هدیه دارد که ارزش هدیه‌ی $i$-اُم، $a_i$ است.

لیته ایده‌ی عجیبی دارد و می‌خواهد زیرمجموعه‌ای از هدیه‌ها را انتخاب کند که میانگین ارزش اعضای آن زیرمجموعه، $k$-امین مقدار را بین مقدارهای ممکن در همه زیرمجموعه‌های ناتهی داشته باشد. (فرض کنید این $2^n - 1$ مقدار را صعودی مرتب کنیم و عضو $k$-اُم را انتخاب کنیم)

با این که ممکن است ارزش چند هدیه با هم برابر باشد، باز هم همه‌ی $2^n - 1$ زیرمجموعه‌ی ناتهی آن در این محاسبات در نظر گرفته می‌شود.

این‌ بار لیته کمک زیادی از شما نمی‌خواهد، فقط می‌خواهد $k$-اُمین مقدار را برای او پیدا کنید.

ورودی🔗

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

در سطر دوم $n$ عدد $a_i$ با فاصله از هم آمده‌اند. $1 \le n \le 60$ $1 \le k \lt 2^n$ $1 \le a_i \le 60\ (1 \le i \le n)$

خروجی🔗

در تنها سطر خروجی عدد جواب را به صورت یک کسر ساده نشدنی چاپ کنید.

ورودی نمونه🔗

4 10
1 2 3 4

خروجی نمونه🔗

8/3

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

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

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

• از یک استراحت‌گاه به یک استراحت‌گاه دیگر حداکثر یک راه مستقیم وجود دارد. (ممکن است بین دو استراحت‌گاه دو راه متفاوت در خلاف جهت یکدیگر وجود داشته باشد)
• از یک استراحت‌گاه به خودش راه مستقیمی وجود ندارد.
• ممکن است در گراف دور وجود داشته باشد.

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

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

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

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

نیمه‌های شب لیته با اتصال به روح مهرسا از زمان همه زمین‌لرزه‌ها و پس‌لرزه‌ها باخبر می‌شود و حالا مدام سوالاتی به ذهنش می‌رسند که اگر در روز $t$-ام اردو در استراحت‌گاه شماره $x$ باشند، آیا ممکن است تا آخر اردو زنده بمانند یا خیر. طبیعتا شما باید در حل این مسئله به او کمک کنید.

ورودی🔗

سطر اول ورودی شامل سه عدد طبیعی $n$ و $m$ و $q$ است که به ترتیب نشان‌دهنده تعداد استراحت‌گاه‌ها، تعداد راه‌های یک‌طرفه بین آن‌ها و تعداد سوالات ذهن لیته هستند.$1 \le n, m, q \le 400\ 000$ در $i$-امین سطر از $n$ سطر بعد اطلاعات لرزش‌های استراحت‌گاه شماره $i$ آمده است، به این صورت که در ابتدا عدد $k$ آمده است که نشاندهنده تعداد لرزش‌های شهر $i$ است و به دنبال آن $k$ عدد مثل $t$ به ترتیب صعودی اکید آمده اند که نشاندهنده‌ی روزهایی هستند که در شهر $i$ لرزش اتفاق افتاده است.

• اولین لرزش هر شهر یک زمین‌لرزه است و بقیه لرزش‌ها در آن شهر پس‌لرزه هستند.
• تضمین می‌شود که زمان تمامی لرزش‌ها متفاوت هستند. یعنی در یک زمان در دو استراحت‌گاه لرزش اتفاق نمی افتد. $0 \le k \le 400\ 000$ $1 \le t \le 10^9$
• هم‌چنین تضمین می‌شود در مجموع تعداد لرزش ها کمتر مساوی $400\ 000$ می‌باشد.

در هر یک از $m$ سطر بعد دو عدد $v$ و $u$ آمده‌است که نشان‌دهنده وجود مسیر یک‌طرفه از استراحت‌گاه شماره $v$ به استراحت‌گاه شماره $u$ است. $1 \le v, u \le n$ در هر یک از $q$ سطر بعد به ترتیب دو عدد $x$ و $t$ آمده‌است که نشان‌دهنده یکی از سوالات ذهن لیته است. (آیا اگر آنها در روز $t$ در استراحت‌گاه شماره $x$ باشند می‌میرند یا زنده خواهند ماند) $1 \le t \le 10^9$ $1 \le x \le n$

خروجی🔗

به ازای هر سوال ذهن لیته، اگر پاسخ سوال این است که زنده خواهند ماند کلمه Alive را چاپ کنید و در غیر این‌صورت کلمه Dead را چاپ کنید.

ورودی نمونه🔗

4 4 4
2 2 4
3 1 5 7
1 6
1 10
1 2
2 3
3 1
2 4
2 5
2 6
1 4
1 5

خروجی نمونه🔗

Dead
Alive
Dead
Alive

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

اگر در زمان ۵ در استراحت‌گاه ۲ باشند (پرسش اول) قطعا می‌میرند زیرا چه به استراحت‌گاه ۳ (در زمان ۶) بروند چه استراحت‌گاه ۴ (در زمان ۱۰) می‌میرند.

اگر در زمان ۶ در استراحت‌گاه ۲ باشند (پرسش دوم) می‌توانند در زمان ۷ پس لرزه می‌آید و آنها با رفتن به استراحت‌گاه ۳ زنده می‌مانند. زیرا در زمان ۸ به استراحت‌گاه ۳ می‌رسند و دیگر زلزله‌ای نمی‌آید.

اگر در زمان ۴ در استراحت‌گاه ۱ باشند (پرسش سوم) مجبورند به استراحت‌گاه ۲ بروند و مانند پرسش اول می‌میرند.

اگر در زمان ۵ در استراحت‌گاه ۱ باشند (پرسش چهارم) زلزله‌ای نمی‌آید و همانجا زنده می‌مانند.

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

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

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

فرض کنید یک مجموعه از رشته‌های دودویی (متشکل از ۰ و ۱) داریم، یک گراف جهت‌دار در نظر بگیرید که رأس‌هایش متناظر با این رشته‌ها باشند و از یک رأس مثل $v$ به راس $u$ یال جهت‌دار وجود دارد، اگر و تنها اگر رشته متناظر راس $v$ پیشوندی از رشته متناظر با راس $u$ باشد. زیبایی این مجموعه رشته برابر با کمینه تعداد مسیر‌های مجزا رأسی برای پوشاندن همه رأس های گراف به‌دست آمده‌است. حالا تعداد مجموعه‌هایی از رشته‌های دودویی را بیابید که:

• مجموع طولشان $n$ است.
• زیبایی خود مجموعه برابر $k$ است.

سپس باقی‌مانده تقسیم عدد حاصل را بر $10^9 + 7$ محاسبه کنید. دقّت کنید که در مجموعه، عضو تکراری وجود ندارد و ترتیب اعضا مهم نیست.

توجه کنید که شما باید به ازای چند مقدار مختلف از $n$‌ و $k$ جواب مسئله را محاسبه کنید.

ورودی🔗

خط اول ورودی شامل عدد طبیعی $t$ می‌باشد که نشاندهنده تعداد سوال‌هایی است که شما باید جواب بدهید. در هر یک از $t$ خط بعد دو عدد مثل $n$ و $k$ آمده اند. $1 \le n \le 50$ $1 \le k \le 8$ $1 \le t \le 1\ 000$

خروجی🔗

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

ورودی نمونه🔗

3
1 1
4 2
7 3

خروجی نمونه🔗

2
18
68

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

بله! زمان به سرعت می‌گذرد و لیته و فیته که به سختی به هم پیوند خورده‌اند قصد دارند به یاد خاطراتی که با هم روی سنِ سالن دارند، این بار در افتتاحیه کدکاپ برای شما نیز خاطره سازی کنند.

آن‌ها می‌خواهند این‌کار را با اجرای نمایشی فوق‌العاده روی سن انجام دهند.

روی سنِ سالن افتتاحیه دنباله‌ای از اعداد طبیعی نوشته شده است و لیته و فیته در دو طرف آن ایستاده‌اند. در مرحله $i$-ام یکی از این دو نفر به انتخاب خودشان یکی از اعضای دنباله که بین این دو نفر است و مقدارش برابر با عدد $i$ است را انتخاب می‌کند، خرامان به سمت آن عضو از دنباله می‌رود و روی آن می‌ایستد.

اگر در مرحله‌ی$k$-ام بین لیته و فیته هیچ عضوی با مقدار $k$ وجود نداشته باشد، نمایش به پایان می‌رسد.

فیته متوجه شد این که نمایش تا چند مرحله ادامه داشته باشد به حرکت‌های آن‌ها بستگی دارد. لیته می‌خواهد طوری حرکت‌ها انتخاب کنند تا نمایش بیشترین مقدار ممکن طول بکشد؛ شما به او بگویید که این نمایش حداکثر چندگام طول خواهد کشید.

ورودی🔗

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

در سطر بعد $n$ عدد $a_i$ با فاصله از هم آمده‌اند. $1 \le n \le 100\ 000$ $1 \le a_i \le n\ (1 \le i \le n)$

خروجی🔗

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

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

5
1 2 4 5 3

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

5

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

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

6
1 4 2 3 5 2

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

4