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

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

مدرسه‌ی حلی سه از $n$ دانش آموز تشکیل شده‌است. $n$ کتاب دیفرانسیل از موسسات متمایز بین آن‌ها پخش شده‌است به طوری که هر نفر یک کتاب دارد. کتابی که نفر $i$ام در اختیار دارد از موسسه‌ی $a_i$ام است. در حالی که نفر $i$ام فقط می‌تواند کتاب‌های موسسه‌ی $i$ را مطالعه کند.

می‌خواهیم به هر کس کتاب متناسب او را بدهیم! برای اینکار هر بار می‌توانیم کتاب نفر $i$ ام را با نفر $j$ ام عوض کنیم اگر $j-i| \leq \frac{n}{2} + 1$| باشد.

شما باید دنباله‌ای از جابه‌جایی‌ها بدهید که هر جابه‌جایی به صورت دو عدد $i$ و $j$ است و کتاب‌های نفر $i$ام و $j$ ام را باهم جابه‌جا می‌کند. پس از انجامِ به ترتیب جابه‌جایی‌ها، هر‌ کس باید کتاب متناسب با خودش را داشته باشد(یعنی نفر $i$ام کتاب موسسه‌ی $i$ام را داشته باشد). به علت کمبود زمان تعداد جابه‌جایی‌ها باید کوچکتر مساوی $\frac{3 \cdot n}{2}$ باشد.

ورودی🔗

در خط اول ورودی $n$ تعداد افراد آمده است سپس در خط بعد یک جایگشت از اعداد $1$ تا $n$ به عنوان آرایه‌ی $a$ آمده است. $1 \leq n \leq 200\ 000$ $1 \leq a_i \leq n$

خروجی🔗

در خط اول خروجی $q$ تعداد جابه‌جایی‌ها بیاید. سپس $q$ خط در هر کدام دو عدد $i$ و $j$ باشد که بیانگر جابه‌جایی کتاب‌های $i$ ام و $j$ ام است.با این شرط که $j-i| \leq \frac{n}{2} + 1$| و $q$ کوچکتر مساوی $\frac{3 \cdot n}{2}$ باشد. اگر چند جواب وجود داشت یکی را چاپ کنید.

مثال🔗

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

4
3 2 1 4

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

1
3 1

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

5
5 4 3 2 1

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

4
1 3
3 5
1 3
2 4

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

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

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

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

تعداد این عملیات ها $n$‌تا است.

ما فقط می‌دانیم متن تقلب‌ها رشته‌ای یکّه است. یکّه به این معناست که اگر متن اصلی گزارش برابر رشته‌ی $s$ و متن رمز گشایی شده (که با انجام پشت سر هم عملیات‌ها بدست آمده) برابر رشته‌ی $c$‌باشد. بتوانیم از $c$ با انجام دادن برعکس عملیات‌ها به $s$ برسیم.

انجام برعکس عملیات‌ها به این معناست که اولاً از عملیات آخر شروع کنیم و تا عملیات اول برویم و دوماً اگر در عملیاتی ما $'a'$ را به $'b'$ تبدیل کردیم در برعکس آن, $'b'$ را به $'a'$ تبدیل خواهیم کرد. برای مثال اگر این دو تبدیل ، تمام عملیات‌های ما باشند:

a b
b c

این دو تبدیل(عملیات) برعکس آن خواهد بود:

c b
b a

برای مثال بالا $"aa"$ یک رشته‌ی یکه به طول دو محسوب می‌شود. زیرا اگر عملیات‌های اصلی روی آن انجام شود حاصل $"cc"$ است و اگر عملیات‌های برعکس روی $"cc"$‌ اعمال شود ما دوباره به همان $"aa"$ می‌رسیم. و $"bb"$ یک رشته‌ی یکه نیست! چون اگر عملیات‌های درست روی آن اعمال شود $"cc"$ حاصل می‌شود و همانطور که گفتیم $"cc"$ در انجام دادن برعکس عملیات‌ها به $"aa"$ ختم می‌شود.

می‌خواهیم ببینیم این تقلب‌ها(رشته‌های یکّه) چند حالت مختلف به طول مشخص‌شده دارند؟؟

اما از بد حادثه تعدادی از عملیات‌های پشت سر هم اشتباهاً اضافه شده است. فلذا $q$ پرسش از شما می‌شود به این شکل که برای هر پرسش سه عدد $t, l, r$ داده می‌شود و شما باید باقی مانده تعداد رشته‌های یکه به طول $t$ بر $1e9+7$ را با فرض این که عملیات‌های $l$ تا $r$ حذف شده‌اند چاپ کنید.

ورودی🔗

در خط اول ورودی عدد $n$ می‌آید. سپس در $n$ خط بعدی در هر خط یک جفت حرف می‌آید که نشان دهنده عملیات هاست. در خط $n + 2$ ام عدد $q$ می‌آید که تعداد پرسش هاست و در نهایت $q$ خط که هر کدام نشانگر یک پرسش است.

$1 \leq n,q \leq 200\ 000$

$1 \leq t \leq 200\ 000$

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

تمامی کاراکتر‌های ورودی از حروف لاتین کوچک تشکیل شده‌اند.

خروجی🔗

در $q$ خط خروجی به ازای هر پرسش جواب آن را چاپ نمایید.

مثال🔗

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

2
a b
b c
3
1 1 2
1 1 1
1 2 2

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

26
25
25

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

در دومین پرسش نمی‌توان از $"c"$ به عنوان رشته‌ی ورودی استفاده کرد زیرا بعد از عملیات، همان $"c"$ ماند و اگر مرحله برعکس عملیات را انجام دهیم تبدیل به $"b"$ خواهد شد.

در سومین پرسش نیز نمی‌توان از $"b"$ به عنوان رشته‌ی ورودی استفاده کرد.

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

7
c f
e f
c c
e d
f b
f c
f b
4
1 3 5
2 3 5
1 2 6
1 4 4

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

23
529
24
23

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

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

تبریک! شما کیک پخش‌کن جلسه‌ی کنکور شده‌اید! باید کاری برای حلی سه‌ای هایِ دوست داشتنی انجام دهید! حلی سه‌ای ها از روش‌های پیشرفته‌ی تقلب استفاده می‌کنند! یکی از این روش‌ها درخت تقلب است! به این صورت که هر نفر به یک راس متناظر می‌شود!

از طرف حلی سه‌ای‌ ها(!) از شما خواسته شده که برای تقلب آسان تر کار‌های زیر را بی‌چون و چرا انجام دهید!

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

• 1 p : طبق برنامه یک حلی سه‌ای وارد می‌شود! اگر قبل از ورود این فرد $k$ فرد سر جلسه حضور داشتند ما شماره‌‌ی $k+1$ را به آن فرد اختصاص می‌دهیم و آن را به راس شماره $p$ وصل می‌کنیم.

• d v 2 : دورترین راس از مقر فرماندهی را که با $v$ حداکثر $d$ یال فاصله دارد را پیدا می‌کنیم و آن را گزارش می‌دهیم!

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

ورودی🔗

در خط اول ورودی $q$ تعداد کوئری‌ها می‌آید. سپس $q$ خط هر کدام همان طور که شرح داده شد آمده‌اند. $1 \leq q \leq 200\ 000$ $0 \leq d \leq 1\ 000\ 000\ 000$ در کوئری‌ها تضمین میشود راس $p$ و $v$ در گراف وجود دارند.

خروجی🔗

به ازای هر کوئری نوع دو، جواب آن را چاپ کنید.

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

مثال🔗

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

5
1 1
1 1
2 2 10
1 3
2 2 10

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

2
4

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

9
1 1
1 1
1 2
2 3 3
1 4
2 3 4
1 4
1 6
2 4 2

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

4
5
7

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

رتبه‌ی ۱۶۱ سال بعد: دوره چهار حلی سه کنکور دارند!

رتبه‌ی یک پارسال: اه!اه! پس ۱۶۰ تا بذار رو رتبت!

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

به این منظور جدولی $n \times m$ تعبیه شده است. در سطر $x$ و ستون $y$ به اندازه ی $\max(a + x \times b, c + y\times d)$ جمله می‌نویسیم. حال مجموع تعداد جمله‌ها را از شما می‌خواهیم.

در واقع برای همه‌ی ستون‌ها یک دنباله‌ی حسابی با قدر نسبت $b$ و مقدار اولیه‌ی $a$ و برای همه‌ی سطر‌ها یک دنباله‌ی حسابی با قدر نسبت $d$ و مقدار اولیه $c$ در نظر گرفتیم و در هر خانه به تعداد بیشینه این دو عدد، جمله می‌نویسیم. شما باید جواب را که تعداد کل کلمه هاست به پیمانه‌ی $10 ^ 9 +7$ چاپ کنید.

ورودی🔗

در تنها خط ورودی به ترتیب اعداد $n$، $m$، $a$، $b$، $c$ و $d$ آمده‌اند.

$1 \leq n, m \leq 1\ 000\ 000\ 000$

$0 \leq a,b,c,d \leq 1\ 000\ 000$

خروجی🔗

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

مثال🔗

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

3 3 0 1 0 2

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

21

توضیح نمونه اول :

جفت ها عبارتند از:

(0,0) (0,2) (0,4) 
(1,0) (1,2) (1,4) 
(2,0) (2,2) (2,4) 

که مجموع بیشینه‌های هر جفت برابر با ۲۱ می‌شود.

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

75164 100 97702 84646 95867 454

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

997345518

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

مصطفی جان!

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

شما از طرف شهید چمران مأمور به غذا دادن به نوزادان یتیم‌خانه شدید.

مقدار غذاها نامحدود است. $n$ نوزاد در یک مسیر مستقیم روی تختشان نشسته‌اند. شما می‌توانید از جایگاه هر کدام از نوزادان شروع کنید و راه بروید و به آن‌ها غذا بدهید. فاصله‌ی بین دو تخت متوالی دقیقاً یک ثانیه است و همچنین زمان مورد نیاز برای غذا دادن قابل صرف نظر است.

در ابتدا همه‌ی نوزادان در حال گریه کردن هستند. اگر نوزاد $i$ام $a_i$ ثانیه از آخرین غذا خوردنش گذشته باشد حتما گریه می‌کند، در غیر این صورت حتما ساکت و آرام نشسته است.

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

ورودی🔗

در خط اول ورودی $n$ تعداد خانه‌ها وجود دارد. در خط بعد $n$ عدد پشت سر هم آمده که آرایه‌ی $a$ را مشخص می‌کند. $1 \leq n \leq 200\ 000$

$0 \leq a_i \leq 200\ 000$

خروجی🔗

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

مثال🔗

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

5
4 3 2 1 0

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

YES

از خانه ی اول به خانه ی آخر میرویم.

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

5
5 4 3 0 0

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

NO