Sereja and Ways in the Cube

All submissions for this problem are available.
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 XX' + YY' + ZZ' = 1.
 Two nonconsecutive 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 Xth number in the Yth line of Zth 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 spaceseparated 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 randomlychosen 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.Author:  sereja 
Tester:  xcwgf666 
Tags  sereja 
Date Added:  7102016 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions