Петя решил положить паркет в комнате размером n × m, паркет состоит из досок размером 1 × 2. Когда строители уложили паркет, выяснилось, что его рисунок выглядит совсем не так, как нравится Пете, и строителям придется его переложить.
Однако строители решили, что снимать паркет целиком и потом раскладывать его заново очень сложно, поэтому каждый час они будут делать такую операцию: вынуть какие-то две доски, образующие квадрат 2 × 2, повернуть их на 90 градусов и положить на то же место.
При этом у них нет никаких идей, как с помощью таких операций получить требуемое расположение, и возможно ли это вообще.
Помогите Пете составить план для рабочих или скажите, что это невозможно. План должен содержать не более 100 000 команд.
Выходные данные
В первой строке выведите k — число операций в плане для рабочих. В следующих k строках выведите описания операций. Операция задается координатами (строка и столбец) левой верхней половинки доски, над которыми проводится операция.
Если решения нет, выведите в первой строке -1.
Примечание
В первом примере первой операцией поворачиваем две правые доски, после чего все доски лежат вертикально. После этого второй операцией поворачиваем две левые доски, получаем требуемую конфигурацию.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
ULR
DLR
LRU
LRD
|
2
1 2
1 1
|
|
2
|
4 3
ULR
DLR
LRU
LRD
ULR
DUU
UDD
DLR
|
3
3 1
3 2
2 2
|