Lui Andrei îi plac foarte mult jocurile de tip puzzle. De curând, el a descoperit un joc nou: un cub de dimensiune n format din n•n•n cuburi unitate sub forma unor cămăruţe. Cubul poate fi văzut ca o matrice tridimensionala ale cărei elemente sunt cămăruţele. Două cămăruţe se numesc adiacente dacă au o faţă comună. Astfel, o cămăruţă poate fi adiacentă cu maxim 6 cămăruţe. Scopul jocului este acela de a duce o bilă din cămăruţa de coordonate (1,1,1) în cămăruţa de coordonate (n,n,n). Bila poate trece dintr-o cămăruţă în alta doar dacă acestea sunt adiacente, iar noua cămăruţă este accesibilă din cămăruţa curentă. Fiecare cămăruţă (i,j,k) are asociat un număr xijk a cărui reprezentare binară codifică in ce cămăruţe se poate deplasa bila din aceasta, astfel:

• Dacă bitul 0 din xijk este 1 atunci bila se poate deplasa în (i+1,j,k), altfel nu
• Dacă bitul 1 din xijk este 1 atunci bila se poate deplasa în (i-1,j,k), altfel nu
• Dacă bitul 2 din xijk este 1 atunci bila se poate deplasa în (i,j+1,k), altfel nu
• Dacă bitul 3 din xijk este 1 atunci bila se poate deplasa în (i,j,k+1), altfel nu
• Dacă bitul 4 din xijk este 1 atunci bila se poate deplasa în (i,j-1,k), altfel nu
• Dacă bitul 5 din xijk este 1 atunci bila se poate deplasa în (i,j,k-1), altfel nu

Lungimea unui drum este dată de numărul de cămăruţe prin care trece bila.

Cerința

Cunoscând n, dimensiunea cubului şi valorile asociate fiecărei cămăruţe, determinaţi:

a) cămăruța cu un număr maxim de cămăruțe ce pot fi accesate din ea;
b) un drum de lungime minimă de la cămăruţa (1,1,1) la cămăruţa (n,n,n).

Date de intrare

Fişierul de intrare cub1.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe a doua linie se găseşte un număr natural n care reprezintă dimensiunea cubului. Următoarele linii conţin n matrice pătratice de dimensiune n, reprezentând valorile xijk asociate cămăruţelor, astfel: primele n linii reprezintă valorile x1jk , următoarele n linii valorile x2jk , ş.a.m.d.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai punctul a) din cerință.

În acest caz, în fişierul de ieşire cub1.out se vor scrie pe prima linie trei numere naturale reprezentând coordonatele cămăruței din care pot fi accesate un număr maxim de cămăruțe.

Dacă valoarea lui p este 2, se va rezolva numai punctul b) din cerință.

În acest caz, în fişierul de ieşire cub1.out se va scrie pe prima linie un singur număr natural L, reprezentând lungimea drumului de lungime minimă găsit. Dacă nu există drum, se va afişa -1. Următoarele L linii vor conţine câte 3 numere naturale reprezentând coordonatele cămăruţelor care alcătuiesc drumul găsit.

Restricții și precizări

• 1 ≤ n ≤ 100
• 0 ≤ xijk ≤ 63
• Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.
• La cerința a), dacă există mai multe cămăruțe care respectă cerința dată, se va afișa oricare dintre ele.
• La cerinţa b), dacă există mai multe drumuri de lungime minimă, se poate afişa oricare dintre ele.
• Coordonatele cămăruţelor se afişează în ordinea în care sunt parcurse de către bilă.

Exemplul 1:

cub1.in

1
3
23 6 2
57 1 10
12 23 12
12 1 17
1 48 3
2 7 17
8 8 4
16 4 4
5 8 6

cub1.out

1 2 1

Explicație

p = 1

x121= 57 [111001]
Din cămăruța (1,2,1) se poate ajunge în (2,2,1), (1,2,2) și (1,1,1). Valoarea 3 este numărul maxim de cămăruțe accesibile dintr-o cămăruță.

Atenție! Pentru acest test se rezolvă doar cerința a).

Exemplul 2:

cub1.in

2
3
23 6 2
57 1 10
12 23 12
12 1 17
1 48 3
2 7 17
8 8 4
16 4 4
5 8 6

cub1.out

7
1 1 1
2 1 1
2 1 2
3 1 2
3 1 3
3 2 3
3 3 3

Explicație

p = 2

Lungimea minimă a unui drum este 7.

Iniţial bila se află în (1,1,1). x111= 23 [010111] (bitul de pe poziția 0 este 1) deci bila se poate deplasa în (2,1,1). x211= 12 [001100] (bitul de pe pozitia 3 este 1) deci bila se poate deplasa în (2,1,2). x212= 1 [000001] (bitul de pe pozitia 0 este 1) deci bila se poate deplasa în (3,1,2), ș.a.m.d.

Atenție! Pentru acest test se rezolvă doar cerința b).