F. Копия копии копии
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Все началось с черно-белой картинки, которую можно представить как матрицу $$$n \times m$$$ такую, что все ее элементы равны $$$0$$$ или $$$1$$$. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы пронумерованы от $$$1$$$ до $$$m$$$.

Над картинкой проделали несколько операций (возможно, ноль), каждая — одного из двух типов:

  • выбрать ячейку такую, что она не находится на границе (строка не $$$1$$$ и не $$$n$$$, столбец не $$$1$$$ и не $$$m$$$) и она окружена четырьмя ячейками противоположного цвета (четырьмя нулями, если она единица, и наоборот), и перекрасить ее саму в противоположный цвет;
  • сделать копию текущей картинки.

Обратите внимание, что порядок операций мог быть произвольным, они могут не чередоваться.

Вам сообщили результат: все $$$k$$$ копий, которые были сделаны. Кроме того, вам сообщили первоначальную картинку. Однако, все эти $$$k+1$$$ картинки были перемешаны.

Восстановите последовательность операций. Если существует несколько ответов, то выведите любой из них. Тесты построены из реальной последовательности операций, т. е. хотя бы один ответ всегда существует.

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

В первой строке записаны три целых числа $$$n, m$$$ и $$$k$$$ ($$$3 \le n, m \le 30$$$; $$$0 \le k \le 100$$$) — количество строк, количество столбцов и количество сделанных копий, соответственно.

Затем следуют $$$k+1$$$ картинок — $$$k$$$ копий и первоначальная. Их порядок произвольный.

Каждая картинка состоит из $$$n$$$ строк, в каждой по $$$m$$$ символов, каждый символ — это $$$0$$$ или $$$1$$$. Перед каждой картинкой идет пустая строка.

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

В первой строке выведите одно целое число — номер первоначальной картинки. Картинки пронумерованы от $$$1$$$ до $$$k+1$$$ в порядке, в котором они заданы во входных данных.

Во второй строке выведите одно целое число $$$q$$$ — количество операций.

В каждой из следующих $$$q$$$ строк должна быть записана одна операция. Операции должны быть перечислены в том порядке, в котором они применялись. Каждая операция может быть одного из двух типов:

  • $$$1$$$ $$$x$$$ $$$y$$$ — перекрасить ячейку $$$(x, y)$$$ ($$$y$$$-я ячейка в $$$x$$$-й строке, она не должна лежать на границу и должна быть окружена четырьмя клетками противоположного от себя цвета);
  • $$$2$$$ $$$i$$$ — сделать копию текущей картинки и присвоить ей номер $$$i$$$ (картинка под номером $$$i$$$ должна совпадать с текущей картинкой).

Каждый номер от $$$1$$$ до $$$k+1$$$ должен встречаться в выводе ровно один раз — один из них — это номер первоначальной картинки, остальные $$$k$$$ — аргументы операций второго типа.

Если существует несколько ответов, то выведите любой из них. Тесты построены из реальной последовательности операций, т. е. хотя бы один ответ всегда существует.

Примеры
Входные данные
3 3 1

010
111
010

010
101
010
Выходные данные
2
2
1 2 2
2 1
Входные данные
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
Входные данные
5 3 0

110
010
001
011
001
Выходные данные
1
0