Все началось с черно-белой картинки, которую можно представить как матрицу \(n \times m\) такую, что все ее элементы равны \(0\) или \(1\). Строки пронумерованы от \(1\) до \(n\), столбцы пронумерованы от \(1\) до \(m\).
Над картинкой проделали несколько операций (возможно, ноль), каждая — одного из двух типов:
- выбрать ячейку такую, что она не находится на границе (строка не \(1\) и не \(n\), столбец не \(1\) и не \(m\)) и она окружена четырьмя ячейками противоположного цвета (четырьмя нулями, если она единица, и наоборот), и перекрасить ее саму в противоположный цвет;
- сделать копию текущей картинки.
Обратите внимание, что порядок операций мог быть произвольным, они могут не чередоваться.
Вам сообщили результат: все \(k\) копий, которые были сделаны. Кроме того, вам сообщили первоначальную картинку. Однако, все эти \(k+1\) картинки были перемешаны.
Восстановите последовательность операций. Если существует несколько ответов, то выведите любой из них. Тесты построены из реальной последовательности операций, т. е. хотя бы один ответ всегда существует.
Выходные данные
В первой строке выведите одно целое число — номер первоначальной картинки. Картинки пронумерованы от \(1\) до \(k+1\) в порядке, в котором они заданы во входных данных.
Во второй строке выведите одно целое число \(q\) — количество операций.
В каждой из следующих \(q\) строк должна быть записана одна операция. Операции должны быть перечислены в том порядке, в котором они применялись. Каждая операция может быть одного из двух типов:
- \(1\) \(x\) \(y\) — перекрасить ячейку \((x, y)\) (\(y\)-я ячейка в \(x\)-й строке, она не должна лежать на границу и должна быть окружена четырьмя клетками противоположного от себя цвета);
- \(2\) \(i\) — сделать копию текущей картинки и присвоить ей номер \(i\) (картинка под номером \(i\) должна совпадать с текущей картинкой).
Каждый номер от \(1\) до \(k+1\) должен встречаться в выводе ровно один раз — один из них — это номер первоначальной картинки, остальные \(k\) — аргументы операций второго типа.
Если существует несколько ответов, то выведите любой из них. Тесты построены из реальной последовательности операций, т. е. хотя бы один ответ всегда существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3 1
010
111
010
010
101
010
|
2
2
1 2 2
2 1
|
|
2
|
4 5 3
00000
01000
11100
01000
00000
01000
10100
01000
00000
01010
10100
01000
00000
01000
10100
01000
|
3
5
1 2 4
2 2
2 4
1 3 2
2 1
|
|
3
|
5 3 0
110
010
001
011
001
|
1
0
|