It all started with a black-and-white picture, that can be represented as an $n \times m$ matrix such that all its elements are either $0$ or $1$. The rows are numbered from $1$ to $n$, the columns are numbered from $1$ to $m$.

Several operations were performed on the picture (possibly, zero), each of one of the two kinds:

choose a cell such that it's not on the border (neither row $1$ or $n$, nor column $1$ or $m$) and it's surrounded by four cells of the opposite color (four zeros if it's a one and vice versa) and paint it the opposite color itself;

make a copy of the current picture.

Note that the order of operations could be arbitrary, they were not necessarily alternating.

You are presented with the outcome: all $k$ copies that were made. Additionally, you are given the initial picture. However, all $k+1$ pictures are shuffled.

Restore the sequence of the operations. If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.


-----Input-----

The first line contains three integers $n, m$ and $k$ ($3 \le n, m \le 30$; $0 \le k \le 100$) — the number of rows and columns of the pictures and the number of copies made, respectively.

Then $k+1$ pictures follow — $k$ copies and the initial picture. Their order is arbitrary.

Each picture consists of $n$ lines, each consisting of $m$ characters, each character is either $0$ or $1$. There is an empty line before each picture.


-----Output-----

In the first line, print a single integer — the index of the initial picture. The pictures are numbered from $1$ to $k+1$ in the order they appear in the input.

In the second line, print a single integer $q$ — the number of operations.

Each of the next $q$ lines should contain an operation. The operations should be listed in order they were applied. Each operation is one of two types:

$1$ $x$ $y$ — recolor a cell $(x, y)$ (the $y$-th cell in the $x$-th row, it should not be on the border and it should be surrounded by four cells of opposite color to itself);

$2$ $i$ — make a copy of the current picture and assign it index $i$ (picture with index the $i$ should be equal to the current picture).

Each index from $1$ to $k+1$ should appear in the output exactly once — one of them is the index of the initial picture, the remaining $k$ are arguments of the operations of the second kind.

If there are multiple answers, print any of them. The tests are constructed from the real sequence of operations, i. e. at least one answer always exists.


-----Examples-----

Input
3 3 1

010
111
010

010
101
010
Output
2
2
1 2 2
2 1
Input
4 5 3

00000
01000
11100
01000

00000
01000
10100
01000

00000
01010
10100
01000

00000
01000
10100
01000
Output
3
5
1 2 4
2 2
2 4
1 3 2
2 1
Input
5 3 0

110
010
001
011
001
Output
1
0


-----Note-----

None

Source: codeforces | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Constructive algorithms

Sorting

Implementation


Solutions:
def countHoles(pic):
	h = 0
	for i in range(1, len(pic) - 1):
		for j in range(1, len(pic[i]) - 1):
			h += pic[i + 1][j] == pic[i - 1][j] == pic[i][j - 1] == pic[i][j + 1] and pic[i + 1][j] != pic[i][j]
	return h

def findDiff(pic1, pic2):
	diff = []
	for i in range(len(pic)):
		for j in range(len(pic[i])):
			if pic1[i][j] != pic2[i][j]:
				diff += [(i, j)]
	return diff
(n, m, k) = (int(v) for v in input().split())
pics = []
for i in range(k + 1):
	input()
	pic = []
	for l in range(n):
		pic += [[c for c in input()]]
	pics += [(i, pic)]
sortpics = sorted(pics, key=lambda p: -countHoles(p[1]))
prevpic = sortpics[0][1]
op = []
for (i, pic) in sortpics[1:]:
	diff = findDiff(prevpic, pic)
	for (x, y) in diff:
		op += [(1, x + 1, y + 1)]
	op += [(2, i + 1)]
	prevpic = pic
print(sortpics[0][0] + 1)
print(len(op))
if len(op) != 0:
	print('\n'.join([' '.join((str(v) for v in t)) for t in op]))


(n, m, k) = [int(_) for _ in input().split(' ')]
arrs = []
ind = 0
while ind <= k:
	input()
	arr = []
	for i in range(n):
		arr.append(input())
	tmp = 0
	for (i, row) in enumerate(arr):
		for (j, ch) in enumerate(row):
			if i != 0 and i < n - 1 and (j != 0) and (j < m - 1) and (arr[i - 1][j] != ch) and (arr[i - 1][j] == arr[i + 1][j] == arr[i][j - 1] == arr[i][j + 1]):
				tmp += 1
	arrs.append((arr, tmp, ind + 1))
	ind += 1
arrs.sort(key=lambda x: x[1], reverse=True)
ans = []
for q in range(1, k + 1):
	if arrs[q][1] == arrs[q - 1][1]:
		ans.append([2, arrs[q][2]])
		continue
	for (i, (row1, row2)) in enumerate(zip(arrs[q - 1][0], arrs[q][0])):
		for (j, (ch1, ch2)) in enumerate(zip(row1, row2)):
			if ch1 != ch2:
				ans.append([1, i + 1, j + 1])
	ans.append([2, arrs[q][2]])
print(arrs[0][2])
print(len(ans))
for anss in ans:
	res = ' '.join((str(_) for _ in anss))
	print(res)


(n, m, k) = input('').split(' ')
n = int(n)
m = int(m)
k = int(k)
ts = []
ps = []
for p in range(k + 1):
	_ = input('')
	pic = ''
	for line in range(n):
		pic += input('')
	ps.append(pic)
	w = 0
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			z = i * m + j
			if pic[z] not in (pic[z + 1], pic[z - 1], pic[z + m], pic[z - m]):
				w += 1
	ts.append((n * m - w, p))
ts = sorted(ts)
print(ts[0][1] + 1)
ops = []
for r in range(k):
	pic1 = ps[ts[r][1]]
	pic2 = ps[ts[r + 1][1]]
	for i in range(1, n - 1):
		for j in range(1, m - 1):
			z = i * m + j
			if pic1[z] != pic2[z]:
				ops.append('1 %i %i' % (i + 1, j + 1))
	ops.append('2 ' + str(ts[r + 1][1] + 1))
print(len(ops))
for op in ops:
	print(op)