Рабочее место участника

Зал супермаркета имеет форму прямоугольника размером `M`x`N`, в котором расставлены витрины размером 1x1. Стороны витрин параллельны стенам супермаркета, а расстояния от витрин до стен – целые числа.

В супермаркет привезли новую супервитрину размером `K`x1 и выгрузили в одном из углов супермаркета. Требуется передвинуть ее в противоположный угол супермаркета. При этом ее нельзя поворачивать, а можно лишь передвигать параллельно стенам супермаркета. Напишите программу, которая по плану супермаркета поможет определить, какое наименьшее количество витрин нужно убрать, чтобы передвинуть супервитрину.

В первой строке входного файла записаны три натуральных числа `M`, `N` и `K` (`M,\ N\ ≤\ 100`, `K\ ≤\ M`). Начальное и конечное расположение супервитрины такие, как указано на верхнем рисунке. В следующей строке записано целое неотрицательно число `V` – количество витрин (`0\ ≤\ V\ ≤\ N*M`). В следующих `V` строках входного файла записаны различные пары целых неотрицательных чисел, характеризующие положения витрин. Первое число (от 0 до `M-1`) – расстояние от левой стены супермаркета до витрины, второе (от 0 до `N-1`) – расстояние от нижней стены до витрины (см. нижний рисунок). Гарантируется, что там, где изначально поставили супервитрину, других витрин нет.

В первой строке выходного файла выведите минимальное количество витрин, которые необходимо убрать. Во второй строке выведите возможный маршрут передвижения супервитрины в следующем формате. Выводится строка из заглавных латинских букв, обозначающих следующее:

Количество символов в строке не должно превышать `N`x`M`.

Если возможных маршрутов несколько, то выведите любой из них.

10 10 5
0

0
RUURUURUURUURU

9 3 2
4
2 0
5 1
5 2
8 2

1
URRRDRRRRUU