Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sereja has a cube A of N x N x N cells. The
the cell at position (X, Y, Z) contains a number A[X][Y][Z]. You have to to find a sequence of cells (X[1], Y[1], Z[1]), (X[2], Y[2], Z[2]), ..., (X[K], Y[K], Z[K]) (triples of integers between 1 and N) satisfying the following properties:

The first cell lies on the front side, i.e. X[1] = 1. 
Each pair of consecutive cells in the sequence are adjacent. Here, we say two cells (X, Y, Z), (X', Y', Z') are adjacent if |X-X'| + |Y-Y'| + |Z-Z'| = 1.
Two non-consecutive cells in the sequence are not adjacent. That is, if i and j are two indices into the sequence with i+2 ≤ j then |X[i]-X[j]| + |Y[i]-Y[j]| + |Z[i]-Z[j]| ≠ 1. 
No two cells in the sequence are the same. 

Help Sereja, find such a sequence that maximize the sum of the numbers stored at the cells in the sequence.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains integer N. Then N blocks of input follow where each block consists of N lines, each containing N integers. The X-th number in the Y-th line of Z-th block is the value A[X][Y][Z].

------ Output ------ 

The first line of output for each test case should contain number K - the number of cells in the sequence. The next K lines should contain three space-separated integers: the X,Y,Z indices of the cell.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 50$
$-1000000 ≤ A[i][j][k] ≤ 1000000$

------ Example ------ 

Input:
1
2
1 1
1 1
1 1
1 1

output:
4
1 1 1
1 1 2
1 2 2
2 2 2

------ Test generation ------ 

Each test will contain T=10 test cases and N will always be equal to 50.
There will be  three types of tests:

$Every number in the cube will be from the set {1, 0, -1000000}. The cube will be generated in the following way. Originally it will be filled with only 1s. Then a randomly-chosen 5% of the positions will be filled with 0.
Finally, while less than 20% of the cube consists of -1000000 entries, some subcube will be filled with -1000000 entries.$
$Every number in cube will be from the set {10000, 1000, 100, 1, 0, -1000000}. This will be generated in the same way as previous test, but originally all numbers are random positives number from the set.$
$80% of numbers are positive numbers from the interval [1, 1000000]. 20% are randomly chosen from the set {-1, -10, -100, -1000, -10000, -100000, -1000000}.$

------ Scoring ------ 

For each test case, let S be the sum of values on the selected path. Let W be the average value of positive numbers inside of the cube. Lets Sum be the sum of the values max(S/W, 1) among all test cases. Lets Best be the maximum value of Sum among all participants. Your displayed score will be Sum/Best.

Difficulty: VERY_HARD

Starter code:

Solutions:
import pprint
for t in range(int(input())):
	n = int(input())
	row = []
	col = []
	mat = []
	for h in range(n):
		row = []
		for i in range(n):
			col = []
			col = list(map(int, input().split()))
			row.append(col)
		mat.append(row)
	addr = [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0]]
	tmp = [1, 1, 1]
	print(1 + 3 * (n - 1))
	print(tmp[0], end=' ')
	print(tmp[1], end=' ')
	print(tmp[2])
	for i in range(n - 1):
		tmp[0] = tmp[0] + addr[1][0]
		tmp[1] = tmp[1] + addr[1][1]
		tmp[2] = tmp[2] + addr[1][2]
		print(tmp[0], end=' ')
		print(tmp[1], end=' ')
		print(tmp[2])
		tmp[0] = tmp[0] + addr[2][0]
		tmp[1] = tmp[1] + addr[2][1]
		tmp[2] = tmp[2] + addr[2][2]
		print(tmp[0], end=' ')
		print(tmp[1], end=' ')
		print(tmp[2])
		tmp[0] = tmp[0] + addr[3][0]
		tmp[1] = tmp[1] + addr[3][1]
		tmp[2] = tmp[2] + addr[3][2]
		print(tmp[0], end=' ')
		print(tmp[1], end=' ')
		print(tmp[2])