کارخانه (Factory)

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

• بازه دلخواه $[l, r)$ را انتخاب می‌کند، یک مستطیل که طول آن در بازه $[l, r)$ و عرض آن بازه $[0, \max(a_l, a_{l+1}, \cdots, a_{r-1})]$ می‌کشد و مستطیل را ۹۰ درجه پادساعتگرد می‌چرخاند، سپس فضای خالی زیر جعبه‌ها پر می‌شود. برای درک بهتر به مثال زیر توجه کنید.

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

رئیس کارخانه ستون‌ها را به صورت یک رشته دودویی دراورده است به طوری که هر ستون تعدادی $0$ متوالی در رشته است که با $1$ از یکدیگر جدا می‌شوند و خود ۱ نیز در آن حساب می‌شود. به طور مثال در شکل ۱ که دنباله ستون‌ها $\langle 3, 4, 2, 5, 6, 5 \rangle$ می‌باشد، رشته آن برابر $0010001010000100000100001$ می‌باشد. تضمین می‌شود که آخرین حرف این رشته حتما $1$ است.

در خط اول ورودی سه عدد طبیعی $n$ طول رشته، $m$ تعداد ستون‌ها و $k$ شماره زیرمسئله به‌ترتیب می‌آیند.

در خط دوم ورودی رشته‌ای دودویی به طول $n$ می‌آید که دقیقا $m$ رقم صفر دارد.

ابتدا تعداد عملیات‌هایی که انجام می‌دهید را چاپ کنید. سپس به‌ترتیب در هر خط بازه‌ای که آن را می‌چرخانید را به صورت $l$ و $r$ چاپ کنید که یعنی بازه $[l, r)$ با شماره‌گذاری‌های جدید را می‌چرخانید.

• $1 \leq n, m \leq 4\,000\,000$
• $1 \leq k \leq 4$
• رشته باینری و اندازه آن برابر $n$ است.

• زیرمسئله اول (۵ نمره): $n \leq 10^3$، حداکثر ۵۰۰ عملیات می‌توانید انجام دهید.
• زیرمسئله دوم (۲۵ نمره): $n \leq 10^5$، حداکثر ۶۵۰ عملیات می‌توانید داشته باشید و اگر $x$ عملیات داشته باشید، نمره شما از این زیرمسئله $min(25, 20 + 5 \times \frac{650 - x}{330})$ خواهد بود.
• زیرمسئله سوم (۲۵ نمره): $n \leq 5 \times 10^5$، حداکثر ۸۵ عملیات می‌توانید انجام دهید.
• زیرمسئله چهارم (۴۵ نمره): $n \leq 4 \times 10^6$ و حداکثر ۱۴۰ عملیات می‌توانید انجام دهید. اگر تعداد عملیات‌های شما $x$ و $100 \leq x \leq 140$ باشد، در صورت $x = 140$ ۱۰ نمره می‌گیرید و $x=100$ ۲۰ نمره و هر مقدار بین این دو به صورت خطی نمره افزایش می‌یابد. اگر $70 < x \leq 100$ ۲۰ نمره می‌گیرید. در صورت $30 \leq x \leq 70$ نیز به صورت خطی بین ۳۰ تا ۴۵ نمره دریافت می‌کنید. در صورت $x \leq 30$ نیز کل نمره را دریافت خواهید کرد.