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

جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. او در تلویزیون تبلیغ همایش «زندگی بهتر برای فردایی بهتر» را مشاهده‌کرد و تصمیم گرفت در همایش شرکت کند! پس از ثبت‌نام و پرداخت پول گزاف برای این همایش در سایت مربوطه، شماره‌ی ردیف و شماره صندلی‌اش در همایش به او ارسال شد.

می‌دانیم این همایش در سالن همایش برج میلاد برگزار می‌شود. این سالن ۱۰ ردیف دارد و هر ردیف آن ۲۰ صندلی دارد. ردیف‌ها از پایین به بالا با ۱ و ۲ و ... و ۱۰ شماره‌گذاری شده‌اند و صندلی‌های هر ردیف از چپ به راست با ۱ و ۲ و ... ۲۰ شماره‌گذاری شده‌اند.

اکنون روز همایش فرا رسیده‌است و جمشید به سالن همایش آمده‌است و از بالا وارد سالن شده‌است. برای آنکه کمتر از میان صندلی‌های یک ردیف عبور کند تا به‌جای خود برسد، اگر شماره صندلی‌اش بین ۱ تا ۱۰ باشد به سمت راست می‌رود و در غیر این‌صورت به سمت چپ می‌رود. از آنجا که سالن تاریک است شماره‌ی ردیف‌ها و صندلی‌ها را نمی‌بیند. برای همین لازم است بداند ردیفش از بالا ردیف چندم است و صندلی‌اش از آن جهتی که وارد ردیف می‌شود صندلی چندم است. برنامه‌ای بنویسید که بگوید به کدام سمت برود و چند ردیف پایین برود و در چندمین صندلی از جهتی که وارد ردیف می‌شود بنشیند.

ورودی🔗

ورودی تنها شامل یک سطر است که در آن به ترتیب دو عدد طبیعی $r$ و $c$ ، شماره‌ی ردیف و شماره صندلی جمشید، آمده‌است. $1 \le r \le 10$ $1 \le c \le 20$

خروجی🔗

در خروجی یک سطر چاپ کنید. اگر جمشید باید به راست برود Right a b و اگر باید به سمت چپ برود Left a b چاپ کنید که a و b به ترتیب شماره ردیف او از بالا و شماره صندلی‌اش از جهتی که وارد می‌شود است.

مثال🔗

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

1 1

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

Right 10 1

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

4 15

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

Left 7 6

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

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

هم‌تیمی‌های استارت-آپ جمشید، فرشید*، *مهشید و نوشید هستند که به همین ترتیب در جهت عقربه‌های ساعت پشت یک میز گرد در کافی‌شاپ خورشید نشسته‌اند. وسط این میز گرد یک ظرف شکلات است که ۴ بخش دارد که در هر بخش تعدادی شکلات وجود دارد. جلوی هریک از ۴ نفر تیم، یک بخش از ظرف قرار دارد. این ۴ نفر با شروع از جمشید، به نوبت و در جهت عقربه‌های ساعت، این روند را تکرار می‌کنند: کسی که نوبتش است از بخشی از ظرف شکلات که روبرویش است یک عدد شکلات می‌خورد، سپس ظرف شکلات را به اندازه ۹۰ درجه در جهت عکس عقربه‌های ساعت می‌چرخاند. این کار را انقدر ادامه می‌دهند تا یکی از این ۴ نفر در بخش جلوییش از ظرف هیچ شکلاتی باقی نماند؛ اینجاست که گارسون رو صدا می‌زنند...

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

ورودی🔗

در تنها خط ورودی ۴ عدد آمده است که به ترتیب برابر تعداد شکلات‌های بخش جلوی جمشید، فرشید، مهشید و نوشید هستند. این بخش‌ها به ترتیب در جهت عقربه‌های ساعت قرار گرفته‌اند. این مقادیر اعدادی طبیعی حداکثر ۱۰۰ هستند.

خروجی🔗

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

مثال🔗

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

3 2 1 3

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

1 1 0 0

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

3 3 5 3

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

2 1 1 1

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

4 2 5 3

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

2 2 2 1

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

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

او پس از چندین بار استفاده از اسنپ و معرفی به دوستان خود و استفاده از کد تخفیف برای سفرهای بعدی متوجه شد که زیرالفبا همه کدهای تخفیف یکسان است. زیرالفبا یک رشته برابر است با مجموعه‌ی حروف متفاوت که در این رشته وجود دارند. برای مثال اگر کد تخفیف XHx2ZLL باشد زیرالفبای آن برابر با $\{2,H,L,X,Z,x\}$ خواهد بود.

امروز یکی از دوستان جمشید به او $n$ کد تخفیف اسنپ، که آن‌ها را با $s_1, s_2, ..., s_n$ نشان می‌دهیم، فرستاده‌است؛‌ جمشید می‌خواهد قبل از استفاده از این کدهای تخفیف مطمئن شود که این کدهای تخفیف معتبر هستند. او برای هر کد تخفیف، می‌خواهد زیرالفبا آن را با زیرالفبای کد تخفیف معتبر و استفاده‌شده $t$ مقایسه کند تا متوجه شود که کدامین کدهای تخفیف معتبر هستند. از آنجا که این فرایند طول خواهد کشید، شما باید برنامه‌ای بنویسید تا مشخص کند هر کد تخفیف معتبر هست یا خیر.

ورودی🔗

سطر اول ورودی شامل عدد طبیعی $n$ و کد تخفیف $t$ است. سپس در $n$ سطر بعدی به ترتیب $s_1$ و $s_2$ و ... و $s_n$ آمده‌است. تضمین می‌شود همه کدهای تخفیف ورودی تنها از حروف کوچک و بزرگ و ارقام انگلیسی تشکیل شده‌اند. $1 \le n \le 100$ $1 \le |s_i|, |t| \le 100$

خروجی🔗

در خروجی باید $n$ سطر چاپ کنید. در سطر $i$ ام Yes چاپ کنید اگر کد تخفیف $i$ ام معتبر است و در غیر این‌صورت No چاپ کنید.

مثال🔗

ورودی نمونه🔗

4 quera102
quEra0012
qu0erraa12
sN0Ap12
qurra00L

خروجی نمونه🔗

No
Yes
No
No

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

جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. جمشید پس از حل معمای بزرگ اسنپ؛ طی ۷۰ روز، خودش را با تکنولوژی‌های روز برنامه‌نویسی آشنا کرد و به سرعت به علت استعدادهای بالایش به عضوی ارشد در اسنپ تبدیل شد. اسنپ می‌خواهد به زودی از سرویس ویژه‌ی خود به نام اسنپ لوکس در خیابان بورس رونمایی کند. آنها قبل از رونمایی باید مسئله‌ی بزرگی را حل کنند و حل این مسئله را به جمشید سپرده‌اند.

خیابان بورس، مرکز بورس ایران، خیابانی طویل و *افقی** است که در یک طرف آن می‌توان ماشین را متوقف نمود. محل پارک توسط شهرداری خط‌کشی شده‌است و کنار این خیابان به ترتیب و پشت سر هم $m+1$ جایگاهِ برای توقف و پارک ماشین وجود دارد که با ۰ تا $m$ از چپ به راست شماره‌گذاری شده‌است. برای پارک کردن در برخی از جایگاه‌های پارک ماشین، باید ماشین مورد نظر برچسب الکترونیکی *الکتروپارک داشته باشد که خیلی خیلی گران‌قیمت است. از آنجا که طول خیابان زیاد است شهرداری این جایگاه‌ها را با $n$ بازه‌ی بدون اشتراک مشخص کرده‌است. بازه $i$ ام بیانگر این است که تمامی جایگاه‌های پارک با شماره بین $l_i$ و $r_i$ (شامل هردو)‌ نیاز به برچسب الکتروپارک دارند. آنها می‌خواهند برای ارائه سرویس بهینه به مردم، ماشین‌های لوکس خود را در این خیابان به صورت آماده‌باش در برخی از این جایگاه‌ها پارک کند. اسنپ در حال حاضر دو ماشین لوکس خود را در جایگاه ۰ و $m$ قرار داده‌است. برای اینکه مردم بتوانند سریع به ماشین خود برسند، هیچ دو ماشین لوکس مجاوری نباید فاصله‌ای بیشتر از ‌$k$ داشته باشند (به عبارتی دیگر در هر $k$ جایگاه پارک متوالی، باید حداقل یک ماشین لوکس وجود داشته باشد). بنابراین ممکن است نیاز داشته باشند ماشین‌های لوکسی در میان این دو جایگاه قرار دهند؛ از این رو اسنپ برای برآورده کردن نیاز مشتری در ابتدا می‌خواهد کمترین تعداد ماشین لوکس را در جایگاه‌های نیازمند الکتروپارک قرار دهد و سپس در بین همه‌ی روش‌های موجود قرار دادن ماشین‌ها با کمترین ماشین در جایگاه نیازمند الکتروپارک، مجموعاً از کمترین تعداد ماشین لوکس استفاده کند. به جمشید کمک کنید تا این مسئله را حل کند تا خودش را به لیدر تیم خود ثابت کند.

ورودی🔗

در سطر اول ورودی، سه عدد صحیح $n$ و $m$ و $k$ آمده‌است. سپس در سطر $i$ از $n$ سطر بعدی به ترتیب دو عدد صحیح $l_i$ و $r_i$ آمده‌است. بازه‌ها در ورودی به صورت صعودی آمده‌اند؛ یعنی $r_i < l_{i+1}$.

تضمین می‌شود هیچ دو بازه‌ای اشتراک ندارند و هیچ کدام شامل جایگاه ۰ و $m$ نیستند.

$1 \le n \le 100\ 000$ $1 \le k \le m \le 10^9$ $1 \le l_i \le r_i \le m - 1$

خروجی🔗

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

مثال🔗

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

2 9 2
3 5
8 8

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

1 4

در پاسخ بهینه برای این نمونه ماشین‌ها در محل‌های پارک ۲، ۴، ۶ و ۷ اضافه می‌شوند که جایگاه شماره ۴ نیاز به برچسب الکتروپارک دارد.

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

2 6 3
1 2
3 4

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

1 1

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

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

جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. او که به مدت طولانی در زندان بوده، از فضای برنامه‌نویسی و کامپیوتر دور شده و می‌خواهد با شرکت در مسابقات برنامه‌نویسی دوباره به این فضا بازگردد. برای همین به سایت کوئرا آمد و بین مسابقات برگزار شده گشت و گذار کرد. در این بین مسابقه‌ی Snapp Challenge توجهش را جلب کرد. نحوه‌ی رتبه‌بندی این مسابقه (مانند همین مسابقه‌ای که اکنون در حال شرکت کردن در آن هستید!) به این شکل بود: شرکت‌کننده‌ها به ترتیب تعداد سوال‌هایی که آن‌ها را کامل حل می‌کنند مرتب می‌شوند. افرادی که به تعداد برابر سوال حل می‌کنند، به ترتیب جریمه*شان مرتب می‌شوند؛ یعنی هر کسی جریمه‌اش کمتر باشد رتبه‌ی بهتری می‌گیرد. مقدار *جریمه به این صورت محاسبه می‌شود:

فرض کنید که مجموع زمان ارسال نهایی شرکت‌کننده برای سوال‌هایی که حل کرده $a$ ثانیه باشد، و برای آن سوال‌ها در مجموع $b$ بار ارسال غلط (قبل از ارسال نهایی) فرستاده است. (مثلاً ارسالی که پاسخ غلط می‌دهد، یا ارسالی که زمان اجرایش مناسب نیست.) در این صورت جریمه‌ی شرکت‌کننده برابر $a + 1200 \times b$ خواهد بود. یعنی هر ارسال غلط مانند ۱۲۰۰ ثانیه (برابر ۲۰ دقیقه) دیرتر فرستادن پاسخ نهایی است.

در نهایت افرادی که هم تعداد سوال برابری حل کرده‌اند و هم جریمه‌شان برابر است، رتبه‌ی برابری می‌گیرند. مثلاُ اگر ۲ نفر رتبه‌ی ۵ بیاورند، نفر بعدی رتبه‌ی ۷ خواهد بود و مسابقه رتبه‌ی ۶ نخواهد داشت. و اگر ۴ نفر رتبه‌ی ۳ بگیرند، نفر بعدی رتبه‌ی ۷ خواهد گرفت و مسابقه رتبه‌های ۴ و ۵ و ۶ نخواهد داشت.

این نحوه‌ی رتبه‌بندی و مخصوصاً ۲۰ دقیقه جریمه برای هر ارسال غلط، جمشید را به فکر فرو برد که آیا این بهترین روش برای رتبه‌بندی است؟ برای همین به این فکر کرد که این زمان ۲۰ دقیقه‌ای را تغییر دهد. مشخص است که مقدار منطقی این عدد ممکن است هر مقدار اعشاری باشد؛ پس برای انتخاب مقدار درست باید بطور خاصی تحلیل انجام داد. او این تحلیل را چنین انجام می‌دهد: فرض کنید رتبه‌ی یک شرکت‌کننده در رتبه‌بندی با فرض ۲۰ دقیقه جریمه، $r$ است. حال فرض کنید که مقدار جریمه به ازای هر ارسال غلط تغییر کند و در رتبه‌بندی که با فرض مقدار جدید صورت می‌گیرد، رتبه‌ی این شرکت‌کننده برابر $r'$ بشود. اگر رتبه‌ی شرکت‌کننده در این حالت بهتر بود (یا $r > r'$)، شرکت‌کننده به مقدار $(r - r')^2$ خوش‌حال می‌شود و اگر رتبه بدتر شده بود، به مقدار $(r' - r)^2$ ناراحت می‌شود که مانند این است که $-(r' - r)^2$ خوش‌حال شده است. حال مجموع میزان خوش‌حال شدن تمامی شرکت‌کننده‌ها در این رتبه‌بندی را میزان خوب بودن مقدار $r'$ برای جریمه‌ی رتبه‌بندی در نظر می‌گیریم.

جمشید که اکنون آدم خوب و خوش‌قلبی شده است، می‌خواهد از روی این معیار که از روی خوش‌حالی افراد تعیین شده رتبه‌بندی‌ها را بسنجد. برای همین به دنبال بیشترین میزان خوب بودن به‌ازای تمامی مقادیر جریمه‌ی ممکن است. (تمام مقادیر صحیح یا اعشاری مثبت یا منفی می‌توانند برای جریمه انتخاب شوند!) با دریافت مقادیر $a$ و $b$ و تعداد سوال‌های حل شده برای هریک از شرکت‌کننده‌های یک مسابقه، بیشترین میزان خوب بودن ممکن برای رتبه‌بندی این مسابقه را محاسبه کنید.

در واقعیت، چنین تحلیلی در رابطه با رتبه‌بندی بهینه در کوئرا انجام شد تا در صورت نیاز مقدار جریمه تغییر بکند!

ورودی🔗

در خط اول ورودی یک عدد $n$ آمده است که تعداد شرکت‌کنندگان در مسابقه را نشان می‌دهد. سپس در هریک از $n$ خط بعدی سه عدد می‌آید که برای یک شرکت‌کننده به ترتیب تعداد سوال حل شده، مقدار $a$ (مجموع زمان ارسال‌های نهایی برای سوال‌های حل شده به ثانیه) و مقدار $b$ (تعداد ارسال‌های غلط برای سوال‌های حل شده) می‌باشند.

تعداد سوال حل شده توسط هر نفر عددی طبیعی و حداکثر ۷ است. $1 \le n \le 100$ $0 \le a \le 86\ 400$ $0 \le b \le 70$

خروجی🔗

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

مثال🔗

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

4
1 100 10
1 100 30
1 100 50
1 100 70

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

14

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

4
1 30 2
1 60 1
2 70 1
2 90 3

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

1

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

جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته می‌شود)، به تازگی آدم شده و از زندان آزاد شده است. اخیراً فرهنگ ترافیکی مردم ذهن او را بسیار آزرده و مشغول خود کرده‌است؛ مسئله‌ای که نمی‌تواند به راه حلی برای آن برسد.

او اکنون دارد در پارک ایران‌زمین قدم می‌زند. این پارک به طرز عجیبی تنها شامل یک خیابان افقی است که از تعداد تقریبا بیشماری بلوک متوالی تشکیل شده‌است. فرض کنید بلوکی که جمشید روی آن قرار دارد بلوک شماره ۰ ام است و بلوک‌های سمت راست آن به ترتیب با ۱ و ۲ و ... نام‌گذاری شده‌اند و بلوک‌های سمت چپ او به ترتیب با ۱- و ۲- و ... نام‌گذاری شده‌اند. در $n$ بلوک با شماره‌های متفاوت $a_1, a_2, ..., a_n$ گل کاشته شده‌است. جمشید در هر دقیقه به صورت کاملا تصادفی یا یک بلوک به سمت راست می‌رود و یا یک بلوک به سمت چپ می‌رود؛ اگر او روی بلوکی برود که روی آن گل قرار دارد و تاکنون له نشده‌است بدون آنکه متوجه شود گل‌های آن بلوک را له می‌کند. او مجموعا $k$ دقیقه پیاده‌روی می‌کند. او پس از فهمیدن اینکه گل‌ها دارند له می‌شوند، برای تسکین ضرری که به پارک زده‌است، می‌خواهد برای هر حالت حرکت ممکن خود در $k$ دقیقه (از $2^k$ حالت متفاوت چپ و راست رفتن در هر دقیقه) تعداد گل‌های له شده را بشمارد و سپس به اندازه‌ی مجموع تعداد گل‌های له‌شده در همه حالات، پول به صندوق کمک‌های مردمی به پارک بیاندازد. از آنجا که این عدد ممکن است خیلی بزرگ شود او تصمیم گرفته‌است باقی‌مانده این عدد بر $10^9+7$ تومان پول به صندوق بیاندازد. به او کمک کنید و مبلغی که باید به صندوق بپردازد را مشخص کنید.

ورودی🔗

سطر اول ورودی شامل دو عدد صحیح $n$ و $k$ است. سپس در سطر بعد $n$ عدد صحیح متفاوت $a_1, a_2, ..., a_n$ آمده‌است. $1 \le n, k \le 5\ 000$ $-5\ 000 \le a_i \le 5\ 000$ $a_i \ne 0$

خروجی🔗

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

مثال🔗

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

1 2
1

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

2

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

4 5
-1 3 2 4

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

43

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

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

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

در تبلیغ رشته‌ای متشکل از دو حرف $0$ و $1$ داده شده است و بازه‌هایی زیبا در آن مشخص شده است. به مجموعه‌ای از بازه‌ها زیبا می‌گوییم اگر هر دو بازه‌ای یا با یک‌دیگر اشتراک نداشته باشند یا یکی کاملا درون دیگری باشد. جمشید متوجه شد که در یک عملیات می‌توانیم یک بازه را انتخاب کرده و حروف آن‌بازه (شامل دو سر) را برعکس کنیم، اگر این‌کار را انجام دهیم، دیگر نمی‌توانیم عملیاتی با این بازه و یا بازه‌های درون آن انجام دهیم . برای مثال می‌توانیم رشته 01101 را برعکس کنیم و به 10110 برسیم. ما باید بزرگترین رشته ممکن (به لحاظ الفبایی) را بسازیم (و پس از آن باید از این رشته رمزی را بیابیم که ما را به سایتی هدایت خواهد کرد، به این بخش فکر نکنید زیرا تنها جمشید از پس حل این معما بر می‌آید!). به جمشید کمک کنید تا برای هر رشته‌ای و هر مجموعه بازه‌های زیبا روی آن، بزرگترین رشته ممکن (به لحاظ الفبایی) که می‌توان ساخت را پیدا کند.

ورودی🔗

در سطر اول ورودی به ترتیب $n$، تعداد بازه‌هایی که مجاز به برعکس کردن آن‌ها هستیم و $s$، رشته اولیه که تنها از $0$ و $1$ تشکیل شده است آمده‌است. سپس در سطر $i$ از $n$ سطر بعدی دو عدد $l_i$ و $r_i$ آمده‌است که بیانگر بازه $i$ ام است. تضمین می‌شود بازه‌های ورودی زیبا هستند. $1 \le n \le 200\ 000$ $1 \le |s| \le 200\ 000$ $1 \le l_i < r_i \le |s|$

خروجی🔗

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

مثال🔗

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

2 001100
2 3
2 5

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

010100

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

3 1001101
1 7
3 6
5 6

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

1101001