Folding
در یک صفحهی طلقی شفاف بهطول افقی m و ارتفاع عمودی n، p نقطهی سیاه رسم شده است.
در هر حرکت میتوانیم صفحه را از وسط بهصورت افقی یا عمودی تا کنیم. پس از هر تاکردن مساحت صفحه نصف میشود و
ممکن است برخی از نقاط روی هم قرار گیرند، بهطوری که وقتی به صفحه شفاف مینگریم به صورت یک نقطه دیده شوند.
میخواهیم با انجام دقیقاً k عمل تاکردن، کاری کنیم که کمترین تعداد نقطه در صفحهی تا خورده دیده شود.
دقت کنید که پس از هر تا طول و عرض طلق باید اعداد طبیعی باقی بمانند.
ورودی
در سطر اول، بهترتیب m، n، p و k داده میشوند.
سپس در هر یک از p سطر بعد، مختصه یک نقطه بهصورت طول و ارتفاع آن (نسبت به گوشهی پایین و سمت چپ صفحه) آمده است.
1≤k≤100
1≤p≤50000
m×n مضربی از 2k می باشد.
همه اعداد ورودی صحیح، نامنفی و کوچکتر از 264 هستند.
خروجی
در سطر اول خروجی کمترین تعداد نقاط قابل رویت پس از k حرکت را بنویسید.
در سطر بعد رشتهای به طول k نویسه بنویسد که نوع هر یک از k عمل تا کردن نشان دهد.
اگر مساله چند جواب بهینه داشته باشد، رشتهی جوابی را چاپ کنید که به لحاظ ترتیب الفبایی (Lexicographical Order) نخستین باشد.
محدودیتها
ورودی و خروجی نمونه
ورودی نمونه | خروجی نمونه |
16 4 6 2
1 1
2 2
1 3
15 1
14 2
15 3 | 2
BL |