E. Головоломка из фишек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Егор придумал новую головоломку из фишек, в которую предлагает сыграть вам.

Головоломка имеет вид таблицы из $$$n$$$ строк и $$$m$$$ столбцов, в каждой клетке которой могут располагаться несколько черных и белых фишек, положенных в ряд. Таким образом, состояние в клетке можно описать строкой, состоящей из символов «0» (белая фишка) и «1» (черная фишка), возможно пустой, а вся головоломка — это таблица, в каждой клетке которой стоит строка из нулей и единиц. Задача состоит в том, чтобы из одного состояния таблицы получить другое.

Для этого можно использовать следующую операцию:

  • выбрать две различные клетки $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, при этом клетки должны находиться в одной строке или одном столбце таблицы, и строка в клетке $$$(x_1, y_1)$$$ должна быть непустой;
  • за операцию можно переместить последний символ строки в клетке $$$(x_1, y_1)$$$ в начало строки в клетке $$$(x_2, y_2)$$$.

Для вас Егор загадал 2 состояния таблицы — начальное и конечное. Гарантируется, что количества нулей и единиц в таблицах совпадают. Ваша задача — с помощью нескольких операций получить из начального состояния конечное. Конечно, Егор не хочет, чтобы количество операций было очень большим. Обозначим за $$$s$$$ количество символов в каждой из таблиц (в таблицах поровну символов). Тогда вы должны использовать не более $$$4 \cdot s$$$ операций.

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

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$2 \leq n, m \leq 300$$$) — количества строк и столбцов у таблиц в головоломке, соответственно.

В следующих $$$n$$$ строках находится описание начального состояния таблицы в следующем формате: в каждой строке находится $$$m$$$ непустых строк, состоящих из нулей и единиц. В $$$i$$$-й из этих строк, $$$j$$$-я строка описывает строку, записанную в клетке $$$(i, j)$$$. Строки нумеруются от $$$1$$$ до $$$n$$$, столбцы нумеруются от $$$1$$$ до $$$m$$$.

В следующих $$$n$$$ строках находится описание конечного состояния таблицы в аналогичном формате.

Обозначим суммарную длину строк в начальном состоянии за $$$s$$$. Гарантируется, что $$$s \leq 100\, 000$$$. Также гарантируется, что количества нулей и единиц совпадают в начальном и конечном состояниях.

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

В первой строке выведите одно целое число $$$q$$$ — количество использованных операций. Необходимо найти решение, для которого $$$0 \leq q \leq 4 \cdot s$$$.

В следующих $$$q$$$ строках выведите по 4 целых числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$. $$$i$$$-я из этих строк должна описывать $$$i$$$-ю операцию. Необходимо, чтобы было выполнено $$$1 \leq x_1, x_2 \leq n$$$, $$$1 \leq y_1, y_2 \leq m$$$, $$$(x_1, y_1) \neq (x_2, y_2)$$$, $$$x_1 = x_2$$$ или $$$y_1 = y_2$$$. При этом строка в клетке $$$(x_1, y_1)$$$ должна быть непустой. Данная последовательность операций должна переводить таблицу из начального состояния в конечное.

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

Примеры
Входные данные
2 2
00 10
01 11
10 01
10 01
Выходные данные
4
2 1 1 1
1 1 1 2
1 2 2 2
2 2 2 1
Входные данные
2 3
0 0 0
011 1 0
0 0 1
011 0 0
Выходные данные
4
2 2 1 2
1 2 2 2
1 2 1 3
1 3 1 2
Примечание

Рассмотрим первый пример.

  • Текущее состояние таблицы:

    00 10
    01 11

    Первая операция. В клетке $$$(2, 1)$$$ записана строка $$$01$$$. Применяя операцию к двум клеткам $$$(2, 1)$$$ и $$$(1, 1)$$$, мы переносим $$$1$$$ из конца строки $$$01$$$ в начало строки $$$00$$$, получая строку $$$100$$$.

  • Текущее состояние таблицы:

    100 10
    0   11

    Вторая операция. В клетке $$$(1, 1)$$$ записана строка $$$100$$$. Применяя операцию к двум клеткам $$$(1, 1)$$$ и $$$(1, 2)$$$, мы переносим $$$0$$$ из конца строки $$$100$$$ в начало строки $$$10$$$, получая строку $$$010$$$.

  • Текущее состояние таблицы:

    10 010
    0  11

    Третья операция. В клетке $$$(1, 2)$$$ записана строка $$$010$$$. Применяя операцию к двум клеткам $$$(1, 2)$$$ и $$$(2, 2)$$$, мы переносим $$$0$$$ из конца строки $$$010$$$ в начало строки $$$11$$$, получая строку $$$011$$$.

  • Текущее состояние таблицы:

    10 01
    0  011

    Четвертая операция. В клетке $$$(2, 2)$$$ записана строка $$$011$$$. Применяя операцию к двум клеткам $$$(2, 2)$$$ и $$$(2, 1)$$$, мы переносим $$$1$$$ из конца строки $$$011$$$ в начало строки $$$0$$$, получая строку $$$10$$$.

  • Текущее состояние таблицы:

    10 01
    10 01

Можно видеть, что мы получили требуемое состояние таблицы.