معمای بزرگ


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

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

تبلیغ اسنپ

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

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

ورودی🔗

در سطر اول ورودی به ترتیب nn، تعداد بازه‌هایی که مجاز به برعکس کردن آن‌ها هستیم و ss، رشته اولیه که تنها از 00 و 11 تشکیل شده است آمده‌است. سپس در سطر ii از nn سطر بعدی دو عدد lil_i و rir_i آمده‌است که بیانگر بازه ii ام است. تضمین می‌شود بازه‌های ورودی زیبا هستند. 1n200 0001 \le n \le 200\ 000 1s200 0001 \le |s| \le 200\ 000 1li<ris1 \le l_i < r_i \le |s|

خروجی🔗

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

مثال🔗

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

2 001100
2 3
2 5
Plain text

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

010100
Plain text

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

3 1001101
1 7
3 6
5 6
Plain text

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

1101001
Plain text