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