Егор придумал новую головоломку из фишек, в которую предлагает сыграть вам.
Головоломка имеет вид таблицы из \(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\) операций.
Выходные данные
В первой строке выведите одно целое число \(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)\) должна быть непустой. Данная последовательность операций должна переводить таблицу из начального состояния в конечное.
Можно показать, что ответ существует. Если есть несколько возможных решений, выведите любое.
Примечание
Рассмотрим первый пример.
- Текущее состояние таблицы:
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
Можно видеть, что мы получили требуемое состояние таблицы.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
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
|