You are not allowed to perform this action

Folding

در یک صفحه‌ی طلقی شفاف به‌طول افقی $m$ و ارتفاع عمودی $n$، $p$ نقطه‌ی سیاه رسم شده است. در هر حرکت می‌توانیم صفحه را از وسط به‌صورت افقی یا عمودی تا کنیم. پس از هر تاکردن مساحت صفحه نصف می‌شود و ممکن است برخی از نقاط روی هم قرار گیرند، به‌طوری که وقتی به صفحه شفاف می‌نگریم به صورت یک نقطه دیده شوند. می‌خواهیم با انجام دقیقاً $k$ عمل تاکردن، کاری کنیم که کم‌ترین تعداد نقطه در صفحه‌ی تا خورده دیده شود. دقت کنید که پس از هر تا طول و عرض طلق باید اعداد طبیعی باقی بمانند.

ورودی

  • در سطر اول، به‌ترتیب $m$، $n$، $p$ و $k$ داده می‌شوند.
  • سپس در هر یک از $p$ سطر بعد، مختصه‌یک نقطه به‌صورت طول و ارتفاع آن (نسبت به گوشه‌ی پایین و سمت چپ صفحه) آمده است.
  • $1 \leq k \leq 100$
  • $1 \leq p \leq 50000$
  • $m \times n$ مضربی از $2^k$ می‌باشد.
  • همه اعداد ورودی صحیح، نامنفی و کوچکتر از $2^{64}$ هستند.

خروجی

  • در سطر اول خروجی کم‌ترین تعداد نقاط قابل رویت پس از $k$ حرکت را بنویسید.
  • در سطر بعد رشته‌ای به طول $k$ نویسه بنویسد که نوع هر یک از $k$ عمل تا کردن نشان دهد.
    • حرف $i$،ام این رشته نوع تا کردن $i$ ام است. در یک تای افقی اگر نیمه‌ی پایین صفحه روی نیمه‌ی بالای صفحه قرار بگیرد حرف B و اگر نیمه‌ی بالای صفحه روی نیمه‌ی پایین قرار بگیرد حرف T را درج می‌کنیم. به‌همین صورت، اگر پس از یک تای عمودی نیمه سمت چپ صفحه روی نیمه‌ی سمت راست قرار بگیرد حرف L و در حالت برعکس حرف R را در خروجی درج می‌کنیم.
  • اگر مساله چند جواب بهینه داشته باشد، رشته‌ی جوابی را چاپ کنید که به لحاظ ترتیب الفبایی (Lexicographical Order) نخستین باشد.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
16 4 6 2
1 1
2 2
1 3
15 1
14 2
15 3
2
BL
▸ سوال قبل سوال بعد ◂