Să considerăm o tablă de șah de dimensiune n (n este par), în care liniile și coloanele sale sunt numerotate de la 1 la n. Pe această tablă se află, pe fiecare pătrat, câte un număr natural astfel încât suma numerelor de pe pătratele albe este egală cu suma numerelor de pe pătratele negre. Pătratele vecine ale pătratului cu coordonatele (i, j), 1 ≤ i ≤ n, 1 ≤ j ≤ n sunt toate pătratele din lista dată : (i-1, j) , (i, j-1), (i+1, j), (i, j+1) , ale căror coordonate aparțin intervalului [1,n]

Definim două operații:

• 1 i j k p x – adună la valorile două pătrate vecine aflate pe pozițiile (i,j) și (k,p) același număr natural x.
• 2 i j k p – scade din valorile două pătrate vecine aflate pe pozițiile (i,j) și (k,p) valoarea minimă reținută pe cele două poziții.

Cerința

Utilizând un număr cât mai mic de operații de tip 1 sau 2 să se obțină pe tabla de șah numai valori nule.

Date de intrare

Fișierul de intrare sah.in conține pe prima linie numărul natural n, iar pe următoarele n linii se găsesc câte n numere naturale reprezentând câte o linie din matrice.

Date de ieșire

Fișierul de ieșire sah.out va conține mai multe linii. Pe fiecare linie este definită câte o operație, deci va conține fie șase numere dacă operația este de tip 1, fie cinci numere dacă operația este de tip 2.

Restricții și precizări

• 2 ≤ n ≤ 100 și n este par;
• 0 ≤ a[i][j] ≤ 500, pentru 1 ≤ i, j ≤ n;
• 1 ≤ i, j, k, p ≤ n și 0 ≤ |x| < 1.000.000.000;
• 0 ≤ a[i][j] ≤ 1.000.000.000 la orice moment de timp
• Valorile scrise pe aceeași linie în fișierul de intrare, respectiv în fișierul de ieșire sunt separate prin câte un spațiu.
• Dacă la un test numărul de operații pe care-l obțineți este mai mic decât n^2 și operațiile conduc la matricea nulă, atunci veți obține punctajul complet pe acel test.
• Restricțiile precizate sunt pentru fiecare test, punctajul fiind suma punctelor obținute pe fiecare test.
• Valorile scrise pe aceeași linie în fișierul de intrare și în fișierul de ieșire sunt separate prin câte un spațiu.
• Dacă numărul de operații este mai mic decât n2, atunci veți primi 100% din punctajul pe acel test.
• Dacă numărul de operații din intervalul [n2 , 2n2 ], atunci veți primi 100% din punctajul pe acel test.
• Este acceptată orice soluție corectă.

Exemplu:

sah.in

2
7 5
3 1

sah.out

1 2 1 2 2 4
2 1 1 2 1
2 1 2 2 2

Explicație

După prima operație matricea devine:
7 5
7 5
După a doua operație matricea devine:
0 5
0 5
După a treia operație matricea devine:
0 0
0 0