D. Перекладывание паркета
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Петя решил положить паркет в комнате размером n × m, паркет состоит из досок размером 1 × 2. Когда строители уложили паркет, выяснилось, что его рисунок выглядит совсем не так, как нравится Пете, и строителям придется его переложить.

Однако строители решили, что снимать паркет целиком и потом раскладывать его заново очень сложно, поэтому каждый час они будут делать такую операцию: вынуть какие-то две доски, образующие квадрат 2 × 2, повернуть их на 90 градусов и положить на то же место.

При этом у них нет никаких идей, как с помощью таких операций получить требуемое расположение, и возможно ли это вообще.

Помогите Пете составить план для рабочих или скажите, что это невозможно. План должен содержать не более 100 000 команд.

Входные данные

Первая строка входных данных содержит числа n и m — размер комнаты (1 ≤ n, m ≤ 50). Хотя бы одно из двух заданных чисел — четно.

Следующие n строк содержат по m символов — описание текущего положения досок паркета. Каждый символ обозначает положение половинки доски. Символы 'L', 'R', 'U' и 'D' соответствуют левой, правой, верхней и нижней половинкам соответственно.

Следующие n строк содержат по m символов содержат описание требуемой конфигурации в том же формате.

Выходные данные

В первой строке выведите k — число операций в плане для рабочих. В следующих k строках выведите описания операций. Операция задается координатами (строка и столбец) левой верхней половинки доски, над которыми проводится операция.

Если решения нет, выведите в первой строке -1.

Примеры
Входные данные
2 3
ULR
DLR
LRU
LRD
Выходные данные
2
1 2
1 1
Входные данные
4 3
ULR
DLR
LRU
LRD
ULR
DUU
UDD
DLR
Выходные данные
3
3 1
3 2
2 2
Примечание

В первом примере первой операцией поворачиваем две правые доски, после чего все доски лежат вертикально. После этого второй операцией поворачиваем две левые доски, получаем требуемую конфигурацию.