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

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

سمنو نماد قدرت، خیر و برکت است.

برای مثال سمنوهای برند bitpin بیمه ابوالفضل هستند، ولی سمنوهای برند samanoo بیمه ابوالفضل نیستند. در ورودی به شما نام برند سمنو داده می‌شود، به علی بگویید که این سمنو بیمه ابوالفضل است یا خیر.

ورودی🔗

در سطر اول رشته $s$ نام برند سمنو می‌آید. تضمین می‌شود این رشته فقط از حروف کوچک انگلیسی تشکیل شده و حداکثر ۲۰ کاراکتر داشته باشد.

خروجی🔗

در صورتی که سمنو بیمه ابوالفضل است عبارت Yes و در غیر این صورت No را چاپ کنید.

توجه کنید سیستم داوری به بزرگ و کوچک بودن حروف حساس است.

مثال‌ها🔗

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

bitpin

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

Yes

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

samanoo

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

No

if 1 <= n <= 100:
    # answer of problem
else:
    # print('invalid input')

input('please enter:')

package ir.quera.contest;

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

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

سبزه نماد شادابی و زایش است.

اگر در دو جایگاه پشت سر هم، دانه عدس کاشته شود، از رشد آن‌ها جلوگیری می‌شود. مادربزرگ می‌خواهد به گونه‌ای $k$ دانه عدس را در $n$ جایگاه قرار دهد، تا تعداد این جفت جایگاه‌ها کمترین مقدار ممکن شود. به بیان دیگر مادربزرگ می‌خواهد طوری دانه‌ها را بکارد که تعداد $i$های صحیحی که $1 \leq i \leq n - 1$ است و در هر دو جایگاه‌های $i$ و $i + 1$ دانه عدس قرار گرفته است، کمترین مقدار ممکن شود.

مادربزرگ به کمک شما برای محاسبه این کمترین مقدار احتیاج دارد.

ورودی🔗

در سطر اول دو عدد صحیح $n$ و $k$ به‌ترتیب می‌آیند. $2 \leq n \leq 100$ $1 \leq k \leq n$

خروجی🔗

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

مثال‌ها🔗

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

5 2

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

0

در این مثال مادربزرگ می‌تواند در جایگاه‌های $1$ و $4$ دو عدس خود را بکارد و هیچ دو عدسی در مجاورت یکدیگر قرار ندارند.

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

5 4

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

2

در این مثال مادربزرگ می‌تواند در جایگاه‌های $1$، $2$، $3$ و $5$ چهار عدس خود را بکارد. جفت جایگاه‌های $(1, 2)$ و $(2, 3)$ در مجاورت یکدیگرند و در هر دو عدس کاشته شده است.

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

صرافی ارز دیجیتال بیت‌پین $n$ رمزارز مختلف دارد که با اعداد $1$ تا $n$ شماره‌گذاری شده‌اند، هر کدام از رمز‌ارزها دو رو دارند. یک رو قدرت که عدد نوشته شده بر آن عدد قدرت آن رمزارز نامیده می‌شود و آن را با $p_i$ نشان می‌دهیم. یک رو زیبایی که عدد نوشته شده بر آن عدد زیبایی آن رمزارز را مشخص می‌کند و آن را با $b_i$ نشان می‌دهیم.

سکه نماد رونق و ثروت است.

دو عدد به نام اعداد زیبایی و قدرت سال وجود دارد که عدد زیبایی سال از بین اعداد زیبایی نوشته شده روی رمزارزها انتخاب می‌شود و عدد قدرت سال نیز از بین اعداد قدرت نوشته شده بر روی رمز ارزها انتخاب می‌شود. قدرت سال را با $P$ و زیبایی سال را با $B$ نشان می‌دهیم. هر رمزارز اگر حداقل یکی از عدد قدرت و یا زیبایی آن بیشتر و یا مساوی عدد متناظرش در سال باشد، می‌تواند به‌جای سکه بر روی سفره هفت سین قرار بگیرد. به بیان دیگر رمزارز شماره‌ی $i$ روی میز قرار می‌گیرد اگر $p_i \geq P$ یا $b_i \geq B$ باشد ($1 \leq i \leq n$).

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

برای شما $t$ بار این مسأله از اول مطرح می‌شود و هر بار از شما می‌خواهیم، این بیشترین مجموع را برای مسأله یا همان تست مد نظر خروجی دهید.

ورودی🔗

در سطر اول عدد $t$، تعداد تست‌ها می‌آید.
در اولین سطر هر تست، عدد صحیح $n$، تعداد بین‌کوین‌های بیت‌پین می‌آید.
در دومین سطر هر تست، $n$ عدد صحیح $b_1, b_2, b_3, \cdots, b_n\,\,$ به‌ترتیب می‌آیند که نشان‌دهنده زیبایی رمزارزهای بیت‌پین است. در سومین سطر هر تست، $n$ عدد صحیح $p_1, p_2, p_3, \cdots, p_n\,\,$ به‌ترتیب می‌آیند که نشان‌دهنده قدرت رمزارزهای بیت‌پین است.

$1 \leq t \leq 200 \, 000$ $1 \le n \le 200 \, 000$ $1 \le b_i, p_i \le 10^9$

تضمین می‌شود که مجموع $n$ برای همه $t$ تست حداکثر $200\,000$ است.

خروجی🔗

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

مثال‌ها🔗

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

3
1
10
13
3
10 3 5
1 3 7
5
1 1 1 1 5
7 1 1 1 1

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

23
13
8

در این ورودی نمونه، ۳ تست مختلف وجود دارد:

• تست اول شامل ۱ رمزارز است. با توجه به اینکه اعداد زیبایی و قدرت از بین اعداد متناظر در رمزارزها باید انتخاب شوند پس عدد زیبایی سال برابر ۱۰ و عدد قدرت برابر ۱۳ خواهد بود، با مجموع ۲۳.
• در تست دوم بیشترین مجموع این است که ۱۰ را به عنوان عدد زیبایی و ۳ را به عنوان عدد قدرت انتخاب کنیم.
• در تست سوم با توجه به اینکه تعدادی رمزارز هستند که زیبایی و قدرت ۱ دارند؛ پس حداقل یکی از زیبایی و قدرت باید ۱ باشد که بتوانند در سفره هفت سین بیایند. بیشترین مجموع ممکن در این مثال را زیبایی ۱ و قدرت ۷ می‌سازد.

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

یک جدول $3 \times n$ داریم. بیت‌پین می‌خواهد تعدادی از خانه‌های جدول را برای عید از سماق پر کند. او به تازگی یاد گرفته است که زیبایی همیشه در تقارن نیست و گاهی زیبایی در بی‌نظمی است. برای همین نگران است که نکند ۴ خانه از خانه‌های جدول باشند که از سماق پر شده باشند و چهار گوشه یک مستطیل از خانه‌های جدول را تشکیل دهند.

سماق نماد صبر و بردباری است.

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

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

ورودی🔗

در سطر اول عدد صحیح $n$ می‌آید که نشان‌دهنده طول جدول است.

$1 \le n \le 100 \, 000$

خروجی🔗

در یک سطر تعداد روش‌های پر کردن سماق در جدول را چاپ کنید.

مثال‌ها🔗

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

1

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

1

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

5

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

540

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

حاجی فیروز تصمیم گرفته برای کمک به نوروز در مزرعه سیری مشغول به کار شود. او شروع کرد به برداشت سیرها و هر مقدار سیری را که در ساعت $i$امش برداشت کرد در گونی‌ شماره $i$ قرار می‌دهد. بعد از اتمام برداشت سیرها متوجه می‌شود در ساعت $i$ام توانسته $a_i$ سیر برداشت کند.

سیر نماد قناعت، مناعت طبع است.

حاجی فیروز که همیشه دنبال پیشرفت است، مقدار پیشرفتش در برداشت سیر در ساعت $i$ام ($1 \lt i$) را برابر مقدار زیر قرار می‌دهد. $max(0, a_i - max_{1 \le j \lt i} a_j)$

که ناگهان $q$ سوال بسیار مهم به ذهن حاجی فیروز رسید. سوال‌های حاجی فیروز دو نوع بودند.

• نوع اول: «چی می‌شد اگر تو ساعت کاری $i$ عوض انقدری که سیر برداشت کردم $x$ سیر برداشت می‌کردم؟»
• نوع دوم: «الان مجموع پیشرفت من از ساعت $l$ تا ساعت $r$ چقدر است؟» (دقت کنید که پیشرفت در ساعت‌های $l$ام و $r$ام هم حساب هستند.)

حواستان باشد که وقتی حاجی فیروز سؤالی از نوع دوم از خودش می‌پرسد تمام تغییراتی که سوال‌های نوع اول که قبل از این سوال به ذهن او خطور کرده است در ذهن او اعمال شده‌اند.

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

ورودی🔗

در سطر اول دو عدد صحیح $n$ و $q$ به‌ترتیب می‌آیند.
در سطر دوم $n$ عدد صحیح $a_1, a_2, a_3, \cdots, a_n\,\,$ به‌ترتیب می‌آیند.
در هر یک از $q$ سطر بعدی سوال‌های حاجی فیروز می‌آیند که هر کدام به یکی از دو شکل زیر است:

• نوع اول: سه عدد $1$ و $i$ و $x$ به‌ترتیب می‌آیند.
• نوع دوم: سه عدد $2$ و $l$ و $r$ به‌ترتیب می‌آیند.

$1 \le n, q \le 2 \times 10^5$ $0 \le a_i \le 10^9$ $1\le i \le n, \quad \quad 0\le x \le 10^9$ $2\le l \le r \le n$

خروجی🔗

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

مثال‌ها🔗

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

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

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

4
4
3

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

در دومین سوال از سوال‌های نوع دوم میزان پیشرفت در ساعت دوم برابر ۱ است، میزان پیشرفت در ساعت سوم ۰ است، میزان پیشرفت در ساعت چهارم ۱ است و میزان پیشرفت در ساعت پنجم نیز ۲ است.

در سومین سوال از سوال‌های نوع دوم میزان پیشرفت در ساعت دوم برابر ۰ است، میزان پیشرفت در ساعت سوم ۰ است، میزان پیشرفت در ساعت چهارم ۱ است و میزان پیشرفت در ساعت پنجم نیز ۲ است.

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

8 8
4 3 7 2 11 5 14 18
2 3 7
2 2 4
1 3 12
2 3 8
2 2 5
1 7 2
1 8 1
2 4 8

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

10
3
14
8
0

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

سرکه نماد پذیرش ناملایمات زندگی است.

یک درخت $n$ راسی داریم که در ابتدا تمام رئوسش به رنگ سرکه‌ای هستند. $q$ پرسمان به شما داده می‌شود. پرسمان‌ها از دو نوع هستند.

• نوع اول: رنگ راس $v$ را عوض کنید. اگر به رنگ سرکه‌ای بود، به رنگ سبز کله غازی در بیاورید و اگر سبز کله غازی بود به رنگ سرکه‌ای در بیاورید.
• نوع دوم: مجموع فاصله‌ی بین تمام جفت راس‌های به رنگ سرکه‌ای را خروجی دهید.

فاصله دو راس برابر تعداد یال‌هایی است که در کوتاه‌ترین مسیر بین دو راس وجود دارد.

ورودی🔗

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

• 1 v: رنگ راس $v$ عوض می‌شود.
• 2: مجموع فواصل را پیدا کنید.

$1 \le n, q \le 10^5$ $1 \le v \le n$

خروجی🔗

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

مثال🔗

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

3 3
1 2
2 3
2
1 2
2

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

4
2

در اولین پرسمان نوع دوم تمام رئوس به رنگ سرکه‌ای هستند و فاصله‌های تمام جفت رئوس سرکه‌ای به نحو زیر است:

فاصله‌ی راس ۱ با راس ۲ برابر ۱ است، فاصله راس ۱ با راس ۳ برابر ۲ است، فاصله راس ۲ با راس ۳ برابر ۱ است.

پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۴ است.

در دومین پرسمان نوع دوم تنها رئوس ۱ و ۳ به رنگ سرکه‌ای هستند و راس ۲ به رنگ سبز کله‌ غازی است.

فاصله‌ی راس ۱ با راس ۳ برابر ۲ است، پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۲ است.

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

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

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

10
6
3
0
2

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

سیب که رنگی نیست، تخم مرغ!

امین با روحیه گرافی خود سعی کرد از ظرف تخم مرغ رنگی روی سفره هفت‌سین سوال طرح کند. او تعداد تخم مرغ رنگی‌های توی ظرف را که $n$ بود شمرد و گراف $G$ را با $n$ راس ساخت. سپس بین هر دو تخم مرغی که با یکدیگر در تماس بودند یال کشید. می‌دانیم رنگ تخم مرغ‌ها با یکدیگر متفاوت است. سپس به ازای هر تخم مرغ لیستی درست کرد که شامل رنگ همان تخم مرغ و رنگ تمام تخم مرغ‌های مجاور با آن در گراف $G$ بود.

‌
سیب نماد سلامتی و زیبایی است.

علی که بسیار شیطون است، همه تخم مرغ‌ها را بی‌رنگ کرد و زیبایی آن‌ها را از بین برد. امین از این اتفاق خوشحال نیست. او می‌خواهد تخم مرغ‌ها را دوباره رنگ کند و ظرف تخم مرغ رنگی‌ها به شکل قبلی خود برگردد. با داشتن گراف $G$ و لیست‌هایی که امین برای هر تخم مرغ درست کرده است، تخم مرغ‌ها را بازآرایی کنید.

ورودی🔗

در سطر اول دو عدد صحیح $n$ و $m$، تعداد تخم مرغ‌ها و تعداد یال‌های میان رئوس متناظر تخم مرغ‌ها به ترتیب می‌آیند.

در هر یک از $m$ سطر بعدی، دو عدد صحیح $v$ و $u$ می‌آیند که یال‌های گراف $G$ را مشخص می‌کنند.

در سطر $i$-ام از $n$ سطر بعدی، $d_i + 1$ عدد صحیح می‌آیند که لیست مربوط به تخم مرغ $i$-ام را مشخص می‌کنند. $d_i$ تعداد تخم مرغ‌های مجاور تخم مرغ $i$-ام است. تضمین می‌شود رنگ‌ها عددی بین $1$ تا $n$ هستند. همچنین تضمین می‌شود حداقل یک حالت برای رنگ‌آمیزی تخم مرغ‌ها وجود دارد.

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

خروجی🔗

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

مثال‌ها🔗

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

4 4
1 2
2 3
3 4
4 1
1 2 3
2 3 4
3 4 1
4 1 2

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

2 3 4 1