Витрина
Зал супермаркета имеет форму прямоугольника размером 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. Если возможных маршрутов несколько, то выведите любой из них.