Scafandrul

Un lac are forma cubică, cu latura $M$ (număr natural). El este împărţit în $M^3$ poziţii elementare. O poziţie (o căsuţă) este identificată prin coordonatele $n$, $l$, $c$, ca întru-un spaţiu tridimensional, unde:

• $n$ reprezintă nivelul ($1$ pentru cel din imediata apropiere a suprafeţei apei, $M$ pentru nivelul de pe fundul lacului),
• $l$ reprezintă linia (linia $1$ este linia cea mai apropiată de privitor)
• $c$ reprezintă coloana (coloana $1$ este cea din stânga privitorului).

Exemplu pentru $m = 4$

Exemple de deplasări elementare:

• din poziţia ($4$, $2$, $2$) se poate ajunge la una din poziţiile: ($3$, $1$, $1$), ($3$, $1$, $2$), ($3$, $1$, $3$), ($3$, $2$, $1$), ($3$, $2$, $2$), ($3$, $2$, $3$), ($3$, $3$, $1$), ($3$, $3$, $2$), ($3$, $3$, $3$);
• din poziţia ($2$, $1$, $1$) se poate ajunge în una din poziţiile: ($1$, $1$, $1$), ($1$, $1$, $2$), ($1$, $2$, $1$), ($1$, $2$, $2$).

Există o căsuţă specială, la suprafaţa apei, considerată pe nivelul $0$ şi anume cea în care trebuie să ajungă în final un scafandru ce pleacă de pe fundul lacului.

În lac există poziţii elementare considerate ca fiind staţii de lucru ce au de transmis la suprafaţă anumite mesaje. Aceste staţii pot fi oricâte şi pot fi dispuse oriunde în cub (chiar şi în poziţia de plecare a scafandrului).

Scafandrul se poate deplasa din poziţia sa numai într-o poziţie de pe nivelul imediat superior (de la nivelul $i$ la nivelelul $i-1$, pentru $1 \leq i \leq m$) şi care diferă ca linie şi coloană cu cel mult $1$ faţă de poziţia precedentă. Deci dintr-o poziţie se poate ajunge (vezi figura) în maxim $9$ poziţii pe nivelul imediat superior.

Scafandrul se află pe fundul lacului la coordonatele $m$, $l_1$, $c_1$. El trebuie să ajungă la suprafaţa lacului (adică deasupra primului nivel al cubului), într-o poziţie de coordonate $0$, $l_2$, $c_2$, adică imediat deasupra poziţiei $1$, $l_2$, $c_2$ din cub.

Cerinţa

Trebuie determinat ce drum trebuie să aleagă scafandrul pentru a duce la destinaţie cât mai multe mesaje, respectând restricţiile din enunţ.

Date de intrare

Fişierul de intrare scafandrul.in, conţine:

• pe prima linie cinci numere $m \ l_1 \ c_1 \ l_2 \ c_2$ despărţite prin câte un spaţiu, reprezentând $m$ dimensiunea cubului, $l_1$, $c_1$ linia şi coloana poziţiei de plecare, iar $l_2$, $c_2$ linia şi coloana poziţiei de sosire;
• pe a doua linie numărul $y$ de staţii din lac;
• pe următoarele $y$ linii seturi de câte patru numere $n \ l \ c \ p$. Primele trei numere $n \ l \ c$ reprezintă coordonatele unei staţii iar ultimul număr $p$ reprezintă numărul de mesaje ce trebuiesc transmise de staţia respectivă;

Date de ieșire

Ieşirea se va face în fişierul scafandrul.out în formatul următor:

• pe prima linie se va scrie numărul maxim de mesaje aduse la suprafaţă.
• pe următoarele $m+1$ linii se vor scrie seturi de patru numere $n \ l \ c \ p$, primele trei numere reprezentând coordonatele staţiilor vizitate (în ordinea parcurgerii), iar ultimul număr reprezentând numărul de mesaje culese din staţia respectivă.

Prima linie din cele $m+1$ reprezintă punctul de plecare, iar ultima punctul de sosire (nivelul $0$).

Restricții și precizări

• $2 \leq M \leq 20$
• $0 \leq P \leq 100$
• Nu este permisă ieşirea din lac decât prin punctul de sosire.
• În punctul de sosire nu se află nici o staţie.
• Dacă pentru o anumită pozitie toate mutările posibile sunt in căsuţe fără staţii, atunci se va scrie in fişierul de ieşire o linie cu coordonatele căsuţei alese şi valoarea $0$ pentru numărul de mesaje (ca pentru o staţie cu $0$ mesaje).

Exemplu

scafandrul.in

3 2 2 2 2
6
1 3 1 10
2 1 3 9
2 2 1 6
2 3 2 7
2 3 3 8
3 2 2 5

scafandrul.out

22
3 2 2 5
2 3 2 7
1 3 1 10
0 2 2 0