· محدودیت حافظه: ۲۵۶ مگابایت
جمشید کاظمی (که با نام مستعار کامران پوریایی شناخته میشود)، به تازگی آدم شده و از زندان آزاد شده است. روزی او مشغول رانندگی در بزرگراه آیت ا... هاشمی رفسنجانی بود که ناگهان تبلیغ معماگونه زیر را از شرکت مورد علاقهاش، اسنپ روی بیلبورد مشاهده کرد.
جمشید پس از چندین هفته بررسی این تبلیغ توانست این معما را حل کند و با حل آن به آدرس سایتی رسید. پس از وارد شدن به سایت متوجه شد اولین نفر است که معما اسنپ را حل کرده و سایت از او خواست که اطلاعاتش را وارد کند. اسنپ فورا با او تماس گرفت و او را با پیشنهاد باورنکردنی جذب خود کرد.
در تبلیغ رشتهای متشکل از دو حرف 000 و 111 داده شده است و بازههایی زیبا در آن مشخص شده است. به مجموعهای از بازهها زیبا میگوییم اگر هر دو بازه ای یا با یک دیگر اشتراک نداشته باشند یا یکی کاملا درون دیگری باشد. جمشید متوجه شد که در یک عملیات میتوانیم یک بازه را انتخاب کرده و حروف آن بازه (شامل دو سر) را برعکس کنیم، اگر اینکار را انجام دهیم، دیگر نمیتوانیم عملیاتی با این بازه و یا بازههای درون آن انجام دهیم . برای مثال می توانیم رشته 01101 را برعکس کنیم و به 10110 برسیم. ما باید بزرگ ترین رشته ممکن (به لحاظ الفبایی) را بسازیم (و پس از آن باید از این رشته رمزی را بیابیم که ما را به سایتی هدایت خواهد کرد، به این بخش فکر نکنید زیرا تنها جمشید از پس حل این معما بر میآید!). به جمشید کمک کنید تا برای هر رشته ای و هر مجموعه بازههای زیبا روی آن، بزرگ ترین رشته ممکن (به لحاظ الفبایی) که می توان ساخت را پیدا کند.
ورودی
در سطر اول ورودی به ترتیب nnn، تعداد بازه هایی که مجاز به برعکس کردن آنها هستیم و sss، رشته اولیه که تنها از 000 و 111 تشکیل شده است آمده است. سپس در سطر iii از nnn سطر بعدی دو عدد lil_ili و rir_iri آمده است که بیانگر بازه iii ام است. تضمین میشود بازههای ورودی زیبا هستند. 1≤n≤200 0001 \le n \le 200\ 0001≤n≤200 000 1≤∣s∣≤200 0001 \le |s| \le 200\ 0001≤∣s∣≤200 000 1≤li<ri≤∣s∣1 \le l_i < r_i \le |s|1≤li<ri≤∣s∣
خروجی
در تنها سطر خروجی، بزرگ ترین رشته ممکن به لحاظ الفبایی که میتوان با جابجایی ها ساخت را چاپ کنید.
مثال
ورودی نمونه ۱
001100 2
3 2
5 2
خروجی نمونه ۱
010100
ورودی نمونه ۲
1001101 3
1 7
3 6
5 6
خروجی نمونه ۲
1101001
مرکز یادگیری سایت تبیان
