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

تابع $D(x)$ را این‌گونه تعریف می‌کنیم که: $x$ + جمع ارقام $x$ + جمع عوامل اول $x$

ما $x$ را پدر $D(x)$ می‌گوییم. برنامه‌ای بنویسید که در خط اول یک $t$ از ورودی خوانده، سپس در $t$ خط بعدی، در هر خط یک عدد از ورودی بگیرد، اگر آن عدد پدر داشت در یک خط Yes و در غیر این صورت No‌ چاپ کند. برای مثال عدد ۱۲، پدر عدد ۲۰ است:

20 = (2+3) + (1+2) + 12

ترجیحاً برای هریک از جمع کردن ارقام یک عدد، پیدا کردن عوامل اول یک عدد و برای محاسبه $D(x)$ یک تابع نوشته شود.

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

ورودی🔗

در خط اول ورودی عدد $t$ آمده و سپس در هریک از $t$ سطر بعدی، یک مقدار $n$ آمده که باید مسئله را برای آن حل بکنید.

$1 \le t \le 100$$4 \le n \le 1\ 000$

خروجی🔗

در $t$ سطر، پاسخ مربوط به هریک عد اعداد ورودی را چاپ کنید.

مثال🔗

ورودی نمونه🔗

2
4
20

خروجی نمونه🔗

No
Yes

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

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

به علی آقا کمک کنید که بداند حداقل جهت چند جاده را باید عوض کند و آن‌ها چه جاده‌هایی هستند.

ورودی🔗

در خط اول دو عدد $n$ و $m$ آمده است و در $m$ خط بعدی مشخصات جاده‌های شکرستان آمده است؛ به گونه‌ای که در خط $i+1$ ام ورودی دو عدد $u_i$ و $v_i$ آمده‌است که نشان می‌دهد جاده‌ی $i$ام از $u_i$ به $v_i$ است. تضمین می‌شود بین هیچ دو تقاطع‌ای بیشتر از یک جاده نیست و علی آقا از شکرستان خوشش می‌آید.

$1 \le n, m \le 1\ 000\ 000$ $1 \le v_i \neq u_i \le n$

خروجی🔗

در خط اول $t$ کمترین تعداد جاده های لازم که علی آقا باید انتخاب کند را چاپ کنید. در خط $t$ خط بعدی شماره جاده‌هایی که علی آقا باید انتخاب کند را به هر ترتیبی چاپ کنید. در صورت وجود چند جواب یکی را به دلخواه چاپ کنید.

مثال🔗

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

2 1
1 2

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

1
1

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

5 7
3 4
2 4
2 3
1 4
1 3
5 3
5 4

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

1
5

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

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

ورودی🔗

در خط اول ورودی عدد $n$ آمده است. در خط بعد دنباله داده شده است. $1 \le n \le 300\ 000$

اعداد دنباله، نامنفی و حداکثر $10^9$ هستند.

خروجی🔗

باقی‌مانده‌ی عدد نهایی پس از انجام این پروسه بر $10^9 + 7$ را چاپ کنید.

مثال🔗

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

4
1 2 3 4

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

0

$1, 2, 3, 4$ $1, 1, 1$ $0, 0$ $0$

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

2
1 2

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

1

$1, 2$ $1$

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

2
2 1

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

1000000006

$2, 1$ $-1$

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

یک جنازه‌ در پارک ملت پیدا شده است. طبق گفته‌های پزشک قانونی، مقتول به وسیله‌ی شات-گان کشته شده و شلیک گلوله‌ی شات-گان در یک لحظه بین لحظه‌ی $L$ و لحظه‌ی $R$ (شامل این دو لحظه) اتفاق افتاده است. کاراگاه شمس می‌خواهد حداقل و حداکثر تعداد ممکن برای افراد حاضر در پارک هنگام شلیک گلوله را بداند. همکار کارآگاه شمس، مادام، لیستی از مظنونین تهیه کرده و طی بازپرسی متوجه شده که مظنون $i$ام از لحظه‌ی $l_i$ تا لحظه‌ی $r_i$ (شامل این دو لحظه)، در پارک حضور داشته است. مادام می‌خواهد با استفاده از این اطلاعات اعداد مدنظر کاراگاه شمس را به او بگوید. البته این کار ساده‌ای نیست، پس به او کمک کنید!

شلیک میتواند در لحظه‌ای اعشاری اتفاق بیفتد.

ورودی🔗

خط اول ورودی شامل دو عدد $L$ و $R$ است.

خط دوم شامل عدد $n$ است که بیانگر تعداد مظنونین واقعه می‌باشد. سپس در $n$ خط بعد هریک شامل دو عدد $l_i$ و $r_i$ است.

$0 \le L \le R \le 10^9$

$0 \le l_i \le r_i \le 10^9$

$1 \le n \le 5000$

خروجی🔗

تنها خط خروجی باید شامل دو عدد باشد که برابر با کمترین و بیشترین تعداد ممکن برای افراد حاضر در لحظه‌ی شلیک شات-گان هستند.

ورودی نمونه🔗

6 10
4
1 8
6 8
7 10
8 9

خروجی نمونه🔗

1 4

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

در ابتدا $n$ صف خالی داریم. در هر مرحله،

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

ورودی🔗

در خط اول ورودی دو عدد $n$ و $q$ آمده است که تعداد صف‌ها و تعداد اتفاقات را نشان می‌دهد.

در $q$ خط بعدی در هر خط،

• $1\ x$

یعنی $x$ به انتهای همه‌ی صف‌ها اضافه می‌شود.

• $2\ i\ j$

از ابتدای صف $i$اُم، $j$ عنصر حذف می‌شود. تضمین می‌شود $j$ حداقل صفر و حداکثر به اندازه‌ی طول فعلی صف است.

$1 \le n, q \le 300\ 000$

$1 \le i \le n$

$1 \le x \le 10^9$

خروجی🔗

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

مثال🔗

ورودی نمونه🔗

2 5
1 5
1 17
2 1 1
1 1
2 2 3

خروجی نمونه🔗

5
23

۲ صف داریم و ۵ اتفاق می‌افتد:

1. عدد ۵ به تمامی صف‌ها اضافه می‌شود.
2. عدد ۱۷ به تمامی صف‌ها اضافه می‌شود.
3. از صف اول عنصر ابتدایی (عدد ۵) حذف می‌شود.
4. عدد ۱ به تمامی صف‌ها اضافه می‌شود.
5. از صف دوم ۳ عنصر اول (۵ و ۱۷ و ۱) حذف می‌شود.

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

می‌دانیم روز آزادی بیان جایگاه ویژه‌ای در میان اهالی برره دارد.

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

روش ناسزا گفتن در برره به این ترتیب است که:

• ابتدا یکی از اهالی بالا برره یک ناسزا به پایین برره‌ای‌ها می‌گوید.

• سپس برای این که خشم پایین برره‌ای ها فروکش کند دو نفر از پایین برره‌ای‌ها به بالا برره‌ای‌ها ناسزا می‌گویند.

• در مرحله بعد ۳ نفر از بالا برره‌ای‌ها به پایین برره‌ای‌ها ناسزا می‌گویند.

• و این جریان به همین ترتیب ادامه پیدا می‌کند تا هنگامی که یکی از دو طرف در یک مرحله $K$ ناسزا به طرف دیگر بگوید.

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

کَیانوش که از دور به این ماجرا نگاه می‌کند، آهی عمیق می‌کشد، نگاهی معنادار به دوربین می‌اندازد و طرفی که اول خشمگین می‌شود را به بینندگان نشان می‌دهد. حال شما با گرفتن $K$ در ورودی، بگویید که کَیانوش کدام طرف را نشان داده.

ورودی🔗

در خط اول $K$ داده شده است. $1 \le K \le 100$

خروجی🔗

در تنها خط خروجی در صورتی که ابتدا بالابرره‌ای‌ها خشمگین می‌شوند Bala Barare و در غیر این صورت Payin Barare را چاپ کنید.

مثال🔗

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

1

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

Payin Barare

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

74

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

Bala Barare