Печатная схема

Печатной схемой называется плоская поверхность содержащей узлы и перемычки, соединяющие пары узлов. Мы будем рассматривать печатные схемы специального вида, где все узлы расположены в узлах прямоугольной сетки, а перемычки (вертикальные или горизонтальные) соединяют пары соседних узлов. Печатная схема называется связной, если любые два узла соединены друг с другом последовательностью перемычек. На вход дается печатная схема, где некоторые соседние узлы уже соединены перемычками. К ней необходимо добавить некоторое количество перемычек таким образом, чтобы схема стала связной. Стоимость вертикальной перемычки – 1, а горизонтальной – 2.

Ваша программа должна по начальной печатной схеме определить количество добавляемых перемычек, минимальную стоимость такого добавления, а также вывести сами добавляемые перемычки.

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

Первая строка входного файла INPUT.TXT содержит два натуральных числа N и M – количество строк и количество столбцов соответственно (1 ≤ N, M ≤ 100). Каждый узел определяется своими координатами, нумерация начинается с верхнего левого угла (координаты (1, 1)). Далее дается описание решетки в виде N строк по M чисел. Каждое число обозначает связь узла (i, j) с узлами (i+1, j) и (i, j+1) в следующем формате:

0 – узел (i, j) не соединен ни с одним из узлов (i+1, j) и (i, j+1)

1 – узел (i, j) соединен только с узлом (i+1, j)

2 – узел (i, j) соединен только с узлом (i, j+1)

3 – узел (i, j) соединен и с узлом (i+1, j), и с узлом (i, j+1).

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

Первая строка выходного файла OUTPUT.TXT должна содержать два числа K и V – количество добавленных перемычек и стоимость добавления соответственно. Каждая из следующих K строк должна содержать описание добавленной перемычки в формате i, j, d, где (i, j) – координаты начального узла, а d может принимать значения 1 или 2. d=1 обозначает, что соединены узлы (i, j) и (i+1, j), d=2 – узлы (i, j) и (i, j+1). Если решений несколько – выведите любое из них.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!