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

باز هم عید نزدیک است و چهارشنبه سوری در پیش! اشکان فردی است علاقه مند به ترقه بازی و هر سال تعداد مناسبی از ۳ نوع ترقه a , b و c دارد. او ترقه ها را در هر ثانیه با هم منفجر می‌کند(البته در صورت وجود)، یا اگر ترقه ای موجود نبود دو ترقه دیگر را همزمان منفجر می‌کند و هر ۱۰ ثانیه یک ترقه از هر نوع منفجر می‌کند.

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

ورودی🔗

ورودی تنها شامل یک خط است که در آن ۳ عدد $a$ ، $b$ و $c$ با فاصله از هم آمده است. $0 \le a,b,c \le 10^6$

خروجی🔗

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

مثال🔗

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

1 2 1

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

Ashkan kojast pas?!

از آنجا که در لحظه اول ترقه a و c تمام می‌شوند و در لحظه دوم همه ترقه ها، همسایه نمی‌گوید ‌اشکان نکن!

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

4 6 6

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

Ashkan nakon!
Ashkan nakon!
Ashkan nakon!

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

دانشکده ریاضی و علوم کامپیوتر هر ساله به مناسبت هفته ریاضیات جشن خیام- تورینگ برگزار می‌کند. امسال شورای صنفی بخش ویژه‌ای به این جشن اضافه کرده است که شامل بازی‌های جدیدی‌ست که دانشجویان ابداع کرده‌اند.

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

• اگر یک سمت کارت شامل یک حرف صدادار انگلیسی باشد و سمت دیگر آن یک عدد زوج.
• اگر یک سمت کارت شامل حرف غیر صدادار باشد.

(می‌دانیم حروف صدا دار حروف $a$, $e$, $i$, $u$ و $o$ و اعداد زوج هم 0, 2, 4, 6 و 8 هستند.)

برای مثال اگر یک کارت حاوی حرف a روی یک طرف آن باشد و عدد 6 روی طرف دیگرش آنگاه این کارت خفن است. همچنین اگر یک کارت شامل حرف b باشد و بر روی طرف دیگرش عدد 4 باشد و یا اگر یک کارت شامل حرف f باشد و بر روی طرف دیگرش 5 باشد؛ از آنجایی که این حروف صدا دار نیستند پس این دو کارت نیز خفن خواهند بود.

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

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

دقت کنید که اگر کارتی خفن بود دیگر نیاز به برگرداندنش ندارید.

ورودی🔗

خط اول ورودی شامل عدد طبیعی $T$ است که نشان دهنده تعداد ترکیب‎‌های ورودی خواهد بود. $1 \le T \le 20$ در $T$ خط بعدی در هر خط یک ورودی شامل یک رشته به شما داده می‌شود که نشان دهنده آن سمتی از کارت هاست که قابل مشاهده است. هر کاراکتر از رشته $S$ یک حرف کوچک انگلیسی یا یک عدد یک رقمی است. $(1 \le |S| \le 50)$

خروجی🔗

خروجی برنامه‌ی شما باید شامل $T$ خط باشد که در هر خط کمترین تعداد کارت هایی که باید چرخانده شوند را به ازای هر مجموعه کارت داده شده، چاپ کنید.

مثال🔗

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

2
ee
z

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

2
0

در نمونه اول شما باید هر 2 کارت را برگردانید تا مطمئن شوید که خفن هستند یا خیر! (دقت کنید که درست است حروف دو کارت یکی هستند اما میتواند عدد پشت آنها متفاوت باشد)

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

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

1
2ey5

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

2

در این ورودی شما باید کارت دوم و چهارم را برگردانید.

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

شورای صنفی از دانشگاه درخواست بودجه کرده ولی دانشگاه به جای پول نقد به شورا گوسفند داده است و شورا تصمیم دارد گوسفندان را پرورش بدهد اما ابتدا باید زمین مناسبی خریداری کند.

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

موقعیت $n$ چاه آب به شکل $(x_1,y_1) ,(x_2,y_2) ,...., (x_n,y_n)$ به شما داده شده. شما باید محدوده زمین را به نحوی در نظر بگیرید که دو ساق مثلث منطبق بر محورهای طول و عرض باشد و نیز تمام چاه های آب را شامل شود (چاه های آب داخل و یا روی محیط زمین قرار گیرد) و سپس گردشده‌ی کمترین طول برای وتر مثلث را چاپ کنید.

بدین شکل به دوستان خود کمک کرده اید تا با کمترین هزنیه تمام چاه های آب را در زمین خود قرار دهند._

ورودی🔗

خط اول شامل عدد طبیعی $n$ است. $1 \le n \le 10^5$ هر یک از n خط بعد شامل دو عدد $x_i$ و $y_i$ می‌باشد. $1 \le x_i, y_i \le 10^8$

خروجی🔗

در تنها خط خروجی، کمترین طول برای وتر مثلث مورد نظر را به صورت یک عدد صحیح چاپ کنید.(خروجی باید گرد شده عدد اعشاری باشد.) همچنین می‌دانیم حتما چنین مثلثی وجود دارد.

مثال🔗

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

1
2 1

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

4

اندازه وتر تقریبا برابر است با 4.24 که گرد شده آن می‌شود 4.

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

3
1 3
2 2
1 1

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

6

اندازه وتر تقریبا برابر است با 5.65 که گرد شده آن می‌شود 6.

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

امروز معلم هنر برایش کاری پیش آمده و نتوانست به کلاس بیاید، به همین دلیل معلم ریاضی سر کلاس رفت تا به بچه ها ریاضی یاد بدهد!

او یک لیستی از $N$ عدد را که ممکن است تکراری باشند را به دانش آموزان داده و قرار است دانش آموزان مقدار تابعی را بر مبنای این اعداد به دست بیاورند.

تعریف می‌کنیم: $g(x) = GCD (a[ 0 ], a[ 1 ], a[ 2 ], …, a[ n-1])$ $f(x) = (a[ 0 ] * a[ 1 ] * a[ 2 ] * … * a[ n-1 ])$ بزرگترین مقسوم علیه مشترک = GCD

دانش آموزان باید حاصل $f(x)^{g(x)}$ را محاسبه کنند.

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

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

ورودی🔗

در خط اول ورودی یک عدد طبیعی $N$ داده میشود و در خط دوم $N$ عدد طبیعی که اعضای لیست هستند داده خوهد شد. $1 \le N \le 50$ $1 \le A[ i ] \le 10^3$

خروجی🔗

باقی مانده مقدار تابع را بر $10^9 + 7$ چاپ کنید.

مثال🔗

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

2
2 6

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

144

در این ورودی میبینیم که حاصل تابع $g(x)$ برابر 2 خواهد بود و حاصل تابع $f(x)$ برابر 12 خواهد بود پس جواب نهایی برابر $144 = 12^2$ خواهد شد

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

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

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

جنگ بین شخصیت بازی که نوبهار نام داشت و غول بازی به این گونه است:

فرض کنید نوبهار جانش $h_C$ است و می‌تواند به اندازه $d_C$ به غول آسیب برساند.

و همچنین غول بازی جانش $h_M$ است و می‌تواند به اندازه $d_M$ به نوبهار آسیب بزند

بازی به این صورت اجرا می‌شود

1. در ابتدا نوبهار به غول حمله می‌کند و به اندازه $d_C$ از جان غول کم می‌شود.
2. در مرحله بعد غول به نوبهار حمله می‌کند و جان نوبهار را به اندازه $d_M$ کم می‌کند.
3. به همین ترتیب یکی درمیان به هم حمله می‌کنند تا بازی تمام شود.

بازی وقتی تمام می‌شود که جان یکی از آنها صفر یا کمتر از صفر بشود

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

قبل از اینکه بازی شروع شود پوریا می‌تواند نوبهار را با خرج حداکثر $k$ سکه تقویت کند، او می‌تواند یا سلاح را تقویت کند یا جان نوبهار را!

هر یک تقویت دقیقا یک سکه می‌خواهد و بسته به انتخاب پوریا یا می‌تواند قدرت سلاح خود را به اندازه $w$ افزایش دهد یا نوبهار را به اندازه $a$ افزایش دهد (دقت کنید که با یک سکه میتوان فقط قدرت یکی از جان یا سلاح را افزایش داد)

پوریا که از کلاس امروز خسته بود با دیدن این بازی و محاسباتش خسته‌تر هم شد، پس از شما خواست تا مثل همیشه به او کمک کنید و ببینید که آیا می‌توانید غول را شکست دهید یا نه!

ورودی🔗

خط اول شامل عدد $T$ است. $(1 \le T \le 5 \cdot 10^4)$ هر کدام از $T$ ورودی بعدی شامل سه خط است.

خط اول هر ورودی شامل دو عدد $h_C$ و $d_C$ است که به ترتیب نشان دهنده میزان جان و قدرت سلاح نوبهار است. $(1 \le h_C \le 10^{15})$ $(1 \le d_C \le 10^{9})$ خط دوم هر ورودی شامل دو عدد $h_M$ و $d_M$ است که به ترتیب نشان دهنده میزان جان و قدرت سلاح غول است.

$(1 \le h_M \le 10^{15})$ $(1 \le d_M \le 10^{9})$

خط سوم هر ورودی به ترتیب نشان دهنده‌ی سه عدد $k$ , $w$ و $a$ است که نشان دهنده ماکسیمم تعداد سکه‌هایی که پوریا دارد، میزان قدرت اضافه شده به سلاح نوبهار و میزان جانی که به نوبهار اضافه می‌شود.

$(0 \le k \le 2 \cdot 10^5)$ $(0 \le w \le 10^9)$ $(0 \le a \le 10^{10})$

خروجی🔗

برای هر ورودی چاپ کنید YES اگر پوریا میتواند به استفاده از سکه هایش غول را ببرد، در غیر این صورت NO چاپ کنید.

مثال🔗

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

4
25 4
9 20
1 1 10
25 4
12 20
1 1 10
100 1
45 2
0 4 10
9 2
69 2
4 2 7

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

YES
NO
YES
YES

در مثال اول پوریا می‌تواند یک سکه بپردازد تا سلاح را تقویت کند (قدرت سلاح بعد از تقویت 5 میشود) سپس در حین بازی جان نوبهار و غول به این شکل تغییر میکند: $(h_C, h_M) = (25, 9) \rightarrow (25, 4) \rightarrow (5, 4) \rightarrow (5, -1)$ بنابراین پوریا بازی را برنده می‌شود.

در مثال دوم پوریا هیچ راهی ندارد که در مقابل غول پیروز شود.

در مثال سوم پوریا سکه ای ندارد پس نمی‌تواند هیچ چیزی را تقویت کند اما جان و قدرت اولیه نوبهار توانایی برد غول را دارد.

در مثال چهارم پوریا 4 سکه دارد. برای اینکه در مقابل غول پیروز شود او باید 2 سکه را خرج تقویت سلاح و 2 سکه را خرج تقویت جان نوبهار کند تا برنده شود.

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

متاسفانه معلم ریاضی متوجه کمک شما به دانش‌آموزان در حل سوال «کلاس هنر» شده و مدارکی نیز در این زمینه بدست آورده!!

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

معلم هنر که خود را مسئول این اتفاق می‌داند دلش به حال دانش‌آموزان سوخته و به واسطه آشنایی قدیمی با معلم ریاضی می‌داند رمزهای عبور او به شکل «سه تایی‌‌های خوش‌ترتیب» است. «سه تایی‌ خوش‌ترتیب» سه‌تایی مرتبی‌ست به صورت $(x, y, z)$ که $z$ به $y$ و $y$ به $x$ بخش پذیر است.\ به عنوان مثال $(1, 2, 4)$ سه تایی خوش ترتیب است؛ زیرا $4$ به $2$ و $2$ به $1$ بخش پذیر است. با این اطلاعات شما می‌توانید از لیست‌های داده شده لیستی را که شامل رمزهای عبور است پیدا کنید. به عنوان مثال فرض کنید برای دسترسی به فایل نیاز به 5 رمز عبور دارید پس باید لیستی را پیدا کنید که شامل 5 «سه تایی‌ خوش‌ترتیب» است.

برنامه‌ایی بنویسید که لیستی از اعداد صحیح مثبت را به عنوان ورودی دریافت کند و تعداد «سه تایی‌‌های خوش‌ترتیب» را به شکلی که

$(lst[i], lst[j], lst[k])$ $i < j < k$

به عنوان خروجی چاپ کند.

ورودی🔗

در سطر اول عدد صحیح n به عنوان اندازه‌ی لیست به شما داده می‌شود که $2 \le n \le 2000$ در $n$ خط بعدی عناصر لیست داده می‌شود که $1 \le k \le 999999$

خروجی🔗

تعداد «سه تایی‌‌های خوش‌ترتیب» را چاپ کنید.

مثال🔗

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

6
1
2 
3 
4 
5 
6

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

3

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

4
7
2
6 
12

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

1

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

بعد از اینکه پوریا بازی‌اش تمام شد به حیاط رفت و مطمئن بود دیگر قرار نیست امروز با مسئله ریاضی دست و پنجه نرم کند؛ اما زهی خیال باطل! وقتی وارد حیاط شد $N$ مورچه را دید که هر کدام روی یک راس از یک $N$ ضلعی منتظم قرار دارند (روی هر راس تنها یک مورچه نشسته است). هر چند وقت همه مورچه‌ها باهم تصمیم میگیرند که به راس‌های همسایه خود بروند (یک راس را همسایه گوییم اگر با یک یال به راس مذکور وصل باشد). می‌دانیم که مورچه‌های حیاط پوریا غذا گیرشان نیامده و اعصاب ندارند و اگر یکدیگر را بر روی یک راس ببینند همدیگر را آنقدر می‌زنند تا هر دو بمیرند! (حالتی که دو مورچه به یک راس بروند باعث دعوا می‌شود) پوریا که دلش نمی‌خواست هیچ مورچه‌ای بمیرد برایش سوالی پیش آمد که چقدر احتمال دارد که بعد از هر حرکت همه مورچه ها زنده بمانند؟

او تا به خودش آمد دید باری دیگر مسئله‌ای ریاضی جلویش قرار دارد!

شما که زحمت دو سوال قبل را برای پوریا کشیدید، لطفا این سوال را هم برای او حل کنید :)

مثال🔗

ورودی🔗

در خط اول عدد $T$ داده می‌شود که نشان دهنده تعداد ورودی‌های هر تست نمونه است. $T \le 1000$ در $T$ خط بعد یک عدد $N$ داده می‌شود که نشان دهنده تعداد مورچه هاست. $3 \le N \le 10^{11}$

خروجی🔗

فرض کنید جواب مسئله برابر کسر $P / Q$ باشد. برای هر ورودی حاصل $(10^9 + 7)$ % $(P * Q^{-1})$ را چاپ کنید

• علامت % نشان دهنده باقی مانده است.

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

1
3

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

250000002

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

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

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

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

ورودی🔗

خط اول شامل عدد طبیعی $n$ است. $1 \le n \le 10^6$

خط دوم شامل n عدد با فاصله از هم $h_1, h_2, ..., h_n$ $1 \le h_i \le 10^9$ که $h_i$ برابر ارتفاع ستون i-ام است.

خروجی🔗

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

مثال🔗

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

1
1

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

0

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

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

3
3 2 3

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

8

تمام حالات در تصویر زیر نمایش داده شده‌ است.

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

شورای صنفی که از فروش گوسفندان به درآمد بسیاری رسید، تصمیم گرفت با طراحان مسابقه الگوریتم شرکت بزند. در این شرکت n کارمند به صورت هرمی و سلسله مراتبی مشغول کارند. به صورتی که هر کارمند (به جز رئیس شورا) دقیقا یک مدیر اولیه دارد. رئیس شورا مدیر همه‌ی کارمندان است. (از طریق زنجیره‌ای از مدیران اولیه)

هر کارمند یک مقدار عددی رتبه دارد. رتبه رئیس شورا برابر ۱ می‌باشد و رتبه هر کارمند دیگر برابر رتبه مدیر اولیه او به علاوه ۱ است.

سبحان به عنوان کارمند فعال این شرکت، از جایگزینی هراس دارد و افراد زیادی هم وجود دارند که میتوانند با او جایگزین شوند. او با خودش یک عدد جایگزینی تعریف میکند. برای هر فرد a و b که مدیر او ( نه لزوما اولین مدیر ) است، عدد جایگزینی ($r(a,b)$) a نسبت به b برابر است با تمام زیردستان b که رتبه‌شان از a بیشتر نیست. اما او از آنجا که وسواس زیادی دارد عدد ترس را هم تعریف میکنم که $f_a$ برای فرد a برابر است با مجموع تمام اعداد جایگزینی او نسبت به مدیرهایش. برای مثال داریم: $f_a = \sum_b r(a,b)$ که سیگما روی مجموعه تمام مدیران یعنی b اعمال می‌شود. سبحان نه تنها علاقمند به عدد ترس خودش است، بلکه از آنجا که پیش در دانستیم کنجکاو است می‌خواهد عدد ترس همه‌ی کارمندان را حساب کند و از آنجا که در شرکت مشغول است و زمان زیادی ندارد، از شما می‌خواد برایش این اعداد را حساب کنید.

ورودی🔗

خط اول شامل تنها یک عدد طبیعی n، یعنی تعداد کارمندان است. $1 \le n \le 5*10^5$ خط دوم شامل n عدد $p_1, p_2,...,p_n$ می‌باشد. $0 \le p_i \le n$ $p_i$ برای رئیس شورا ۰ بوده، و برای بقیه $p_i$ها برابر است با شناسه اولین مدیر کارمند با شناسه i. مطمئنیم بین $p_i$ها فقط یک عدد 0 وجود دارد و همچنین رئیس شورا مدیر همه‌ی کارکنان (نه لزوما اولین مدیر)

خروجی🔗

خروجی برنامه‌ی شما باید شامل یک خط باشد، که نشان دهنده عدد ترس هر کارمند به ترتیب شناسه او می‌باشد: $z_1, z_2, ..., z_n$

مثال🔗

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

4
0 1 2 1

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

0 2 4 2 

• رئیس شورا مدیری ندارد. پس $f_1 = 0$
• $r(2,1) = 2$ (کارمندان ۲ و ۴ مورد قبول شرط‌اند و کارمند ۳ رتبه بزرگ تری دارد.). پس $f_2= r(2,1) = 2$
• مانند $f_2$ میدانیم: $f_4 = r(4,1)$
• $r(3,2) = 1$ (کارمند ۳ زیردست کارمند ۲ است و رتبه قابل قبول را دارد.). $r(3,1) = 3$ (کارمندان ۲، ۳ و ۴ در شرط صدق می‌کنند.). بنابراین $f_3 = r(3,2) + r(3,1) = 4$

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

  5
  0 1 1 1 3

  Plain text

  Copy

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

0 3 3 3 5 

• محدودیت زمان: 8 ثانیه
• محدودیت حافظه: 1024 مگابایت

شاید فکر کنید پوریا دست از سر شما برداشته است اما اشتباه می‌کنید! :)

او که دیگر با شما صمیمی شده‌ است نه تنها سوال‌های خودش را به شما می‌دهد بلکه سوال‌های دوستش زهرا را نیز به شما می‌دهد تا حل کنید!

او به شما اعداد $A$, $B$, $V$ و $M$ را می‌دهد به طوری که اعداد $A$ و $B$ همیشه نسبت به هم اول $(Coprime)$ یا همان متباین باشند. همچنین شما عدد $x$ را نیز دارید که در ابتدا $x=V$ است.

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

• عوض کردن مقدار $x$ با $x + A$
• عوض کردن مقدار $x$ با $x - A$
• عوض کردن مقدار $x$ با $x + B$
• عوض کردن مقدار $x$ با $x - B$

این را بدانید که شرط $0 \le x \le M$ در مراحل عملیاتی که انجام می‌دهید باید رعایت شود.

با توجه شرایط فوق چند مقدار مختلف برای $x$ وجود خواهد داشت؟

پوریا به زهرا قول داده که این سوال را برایش حل کند پس لطفا به او کمک کنید تا آبرویش پیش زهرا حفظ شود!

ورودی🔗

در خط اول عدد $T$ داده میشود که نشان دهنده تعداد ورودی‌هاست. در $T$ خط بعدی سه عدد $A$, $B$, $V$ و $M$ داده میشود

ترتیب ورودی هر نمونه : A B V M

خروجی🔗

برای هر ورودی تعداد مقدارهای مختلف برای $x$ را چاپ کنید.

محدودیت ها🔗

$1 \le T \le 10^5$ $1 \le A \le B \le M \le 10^9$ $0 \le V \le M$

مثال🔗

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

5
3 5 0 5
1 2 5 10
5 8 4 9
10 99 48 106
500000000 500000001 123456789 900000000

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

4
11
4
10
800000002

در ورودی اول مقدارهای مختلف و ممکن برای $x = 0, 2, 3, 5$ است

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

زنگ تفریح بعد از کلاس هنر پوریا و هم کلاسی هایش تصمیم گرفتند بازی ای بکنند. همه $N$ دانش آموزان کلاس پشت سر هم بر روی یک صف قرار گرفتند. برای مثال دانش آموز 2 پشت 1 و 3 پشت 2 و به همین ترتیب تا آخر.

شادی یک دانش آموز $i$ ام را اینگونه تعریف میکنیم: تعداد دانش آموزانی که مقابل او قرار دارند و قدشان از او (دانش آموز $i$ام) اکیدا بلند تر است.

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

شما که دیگر از دست پوریا خسته شده اید میخواهید از او انتقام بگیرید

قرار است خوشی کلاس را کمینه کنید تا حال پوریا گرفته شود!

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

ورودی🔗

در خط اول عدد $T$ داده می‌شود $1 \le T \le 5$ در $T$ خط بعدی برای هر خط یک عدد $N$ داده می‌شود که تعداد دانش آموزان است و در خط بعد یک لیستی از $N$ عدد که نشان دهنده قد هر دانش آموز است $h_i$. $1 \le N \le 10^5$ $1 \le h_i \le 10^{10}$

خروجی🔗

برابر هر ورودی نمونه، کمینه خوشی که می‌توانید ایجاد کنید را چاپ کنید.

مثال🔗

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

1
4
4 1 3 2

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

1