Вітрина
Зал супермаркету має форму прямокутника розміром m×n, у якому розставлені вітрини розміром 1×1. Сторони вітрин паралельні стінам супермаркету, а відстані від вітрин до стін цілі числа.
До супермаркету привезли нову супервітрину розміром k×1 і вивантажили у одному з кутів супермаркету. Потрібно пересунути її у протилежний кут супермаркету. При цьому її не можна повертати, а можна лише пересувати паралельно стінам супермаркету. Напишіть програму, яка за планом супермаркету допоможе визначити, яку найменшу кількість вітрин потрібно прибрати, щоб пересунути супервітрину.
Вхідні дані
У першому рядку вхідного файлу записано три натуральних числа M, N та K (M, N ≤ 100, K ≤ M). Початкове та кінцеве розміщення супервітрини такі, як показано на верхньому рисунку. У наступному рядку записано ціле невід'ємне число V – кількість вітрин (0 ≤ V ≤ N·M). У наступних V рядках вхідного файлу записані різні пари цілих невід'ємних чисел, які характеризують положення вітрин. Перше число (від 0 до M−1) – відстань від лівої стіни супермаркету до вітрини, друге (від 0 до N−1) – відстань від нижньої стіни до вітрини. Гарантується, що там, де спочатку поставили супервітрину, інших вітрин немає.
Вихідні дані
У першому рядку вихідного файлу виведіть мінімальну кількість вітрин, які потріьно прибрати. У другому рядку виведіть можливий маршрут пересування супервітрини у наступному форматі. Виводиться рядок з великих латинських букв, які позначають наступне:
U – на 1 вгору,
D – на 1 вниз,
L – на 1 ліворуч,
R – на 1 праворуч.
Кількість символів у рядку не повинна перевищувати NxM. Якщо можливих маршрутів декілька, то виведіть довільний з них.