• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• آزمون عملی سوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران

---

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

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

چرخش بازه \([1, 4)\) . ستون‌ها از \(0\) شماره‌گذاری می‌شوند.

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

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

ورودی

در خط اول ورودی سه عدد طبیعی \(n\) طول رشته، \(m\) تعداد تعداد ستون‌ها و \(k\) شماره زیرمسئله به‌ترتیب می‌آیند. \[1 \leq n, m \leq 4 \, 000 \, 000\] \[1 \leq k \leq 4\]

خروجی

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

زیرمسئله‌ها

توجه کنید که به دلیل محدودیت‌های فعلی امکان نمره دهی جزئی وجود ندارد و مانند سوال های دیگر برای گرفتن نمره‌ی یک زیرمسئله باید آن را کامل حل کرده باشید و حتی اگر طبق امتیاز دهی گفته شده باید قسمتی از نمره یک زیرمسئله را می‌گرفتید برای شما ۰ حساب می‌شود.

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

مثال

ورودی نمونه ۱

15 6 1
100011001001001

خروجی نمونه ۱

6
0 6
1 4
0 7
2 3
1 2
0 1