Cub

Staţia de cercetări astronomice ONI–2006 are forma unui cub cu latura de lungime N unităţi. Fiecare dintre cele 6 feţe ale staţiei este împărţită în $N \times N$ pătrate cu latura unitate. Cosmonauţii însărcinaţi cu întreţinerea staţiei se pot deplasa pe suprafaţa cubului, folosind şine speciale plasate în unele dintre pătrăţelele unitate, pentru a efectua diverse reparaţii. Unele pătrate unitate, dintre cele prevăzute cu şine, conţin trape de intrare în interiorul staţiei. Din cauza radiaţiilor cosmice nocive, cosmonauţii trebuie să petreacă un timp cât mai scurt în exteriorul staţiei astfel încât, după terminarea unei reparaţii, aceştia trebuie să se reîntoarcă în interiorul staţiei utilizând cea mai apropiată trapă de acces. Cosmonautul se află iniţial într-un pătrăţel prevăzut cu şine. El se poate deplasa dintr-un pătraţel ce conţine şine, în altul, aflat în vecinătatea poziţiei curente (pe orizontală sau verticală), pătrăţel prevăzut de asemenea cu şine. Cosmonautul se poate deplasa şi de pe o faţă a cubului pe o faţă vecină, traversând latura comună. Feţele cubului sunt descrise conform figurii de mai jos.

• Faţa 1: $ABCD$ - elementul $(1,1)$ în $A$ şi elementul $(N,N)$ în $C$
• Faţa 2: $DCC’D’$ - elementul $(1,1)$ în $D$ şi elementul $(N,N)$ în $C’$
• Faţa 3: $B’A’D’C’$ - elementul $(1,1)$ în $B’$ şi elementul $(N,N)$ în $D’$
• Faţa 4: $BAA’B’$ - elementul $(1,1)$ în $B$ şi elementul $(N,N)$ în $A’$
• Faţa 5: $CBB’C’$ - elementul $(1,1)$ în $C$ şi elementul $(N,N)$ în $B’$
• Faţa 6: $ADD’A’$ - elementul $(1,1)$ în $A$ şi elementul $(N,N)$ în $D’$

Cerinţă

Scrieţi un program care să determine distanţa minimă de la poziţia iniţială a cosmonautului până la o trapă de acces, precum şi numărul trapelor aflate la distanţă minimă.

Date de intrare

Datele de intrare se citesc din fişierul cub.in, care are următoarea structură: Pe prima linie se află două numere naturale $N$ şi $K$, separate printr-un spaţiu, reprezentând lungimea laturii cubului, respectiv numărul trapelor de acces. Pe a doua linie avem numerele naturale $F$, $L$, $C$, separate prin spaţiu, desemnând pătratul unitate pe care se află iniţial cosmonautul, unde $F \in \{1,2,3,4,5,6\}$ reprezintă numărul unei feţe a cubului, iar $L$ şi $C$ reprezintă coordonatele poziţiei iniţiale a cosmonautului, relative la colţul $(1,1)$ al feţei cu numărul $F$ ($L$ – numărul liniei, $C$ – numărul coloanei). Pe următoarele $K$ linii se află câte $3$ numere naturale, separate prin spaţiu, reprezentând coordonatele celor $K$ trape de acces (numărul feţei, numărul liniei, respectiv numărul coloanei).
Pe următoarele $6 \cdot N$ linii se află cele $6$ matrice pătratice care descriu feţele cubului, având elemente din mulţimea ${0, 1}$ ($0$ – şină de acces, $1$ - pătrat inaccesibil). Elementele unei feţe sunt date pe linii, de la $(1,1)$ până la $(N,N)$.

Date de ieșire

Rezultatele se scriu în fişierul cub.out, care are următoarea structură: Pe prima linie se va scrie numărul natural $LG$, reprezentând lungimea drumului minim parcurs de cosmonaut. Lungimea drumului este dată de numărul pătratelor unitate parcurse, inclusiv poziţia iniţială şi poziţia finală. Pe a doua linie se va afişa numărul natural $T$, reprezentând numărul trapelor de acces aflate la distanţă minimă faţă de poziţia iniţială a cosmonautului.

Restricții și precizări

• $1 \leq N \leq 50$;
• $1 \leq F \leq 6$;
• $1 \leq L, C \leq N$;
• Cosmonautul se află iniţial într-o poziţie accesibilă (prevăzută cu şină);
• Există cel puţin o trapă accesibilă din poziţia iniţială a cosmonautului.

Exemplu

cub.in

3 2
2 2 3
5 2 2
3 2 2
1 1 1
1 0 0
1 0 1
0 0 1
0 1 0
0 0 0
1 1 1
1 0 1
1 1 1
1 1 1
1 1 1
1 1 1
1 0 1
1 0 1
1 1 1
1 1 1
1 1 1
1 1 1

cub.out

12
1

Explicație

Traseul ilustrat are costul minim $12$ şi uneşte elementul $(2,3)$ de pe faţa $2$ cu elementul $(2,2)$ de pe faţa $5$. Cealaltă trapă de acces se află pe faţa $3$, într-o poziţie inaccesibilă, deci numărul trapelor aflate la distanţa minimă faţă de poziţia de start este $1$.