Mascat

Saima Chang are de pregătit un teren înzăpezit pentru jocurile olimpice de iarnă. Terenul este dat printr-o matrice $V$ cu $N$ linii și $M$ coloane, unde $V[i][j]$ reprezintă înălțimea zăpezii din celula $(i, j)$ relativ față de nivelul dorit. Valorile inițiale pot fi negative sau pozitive, dar se dorește ca acestea să devină $0$. Pentru a face asta, Saima Chang își folosește lopata lui de încredere în formă de L. Acesta o poate așeza la o poziție $(x_i, y_i)$ dorită, într-o orientare $P_i$ dorită, și poate lua sau adăuga un număr dorit variabil $A_i$ de zăpadă.

Cerință

Saima Chang are nevoie de ajutor pentru a rezolva $2$ sarcini:

• Fiind dată matricea inițială, aflați dacă există o serie de operații astfel încât aceasta să devină complet nulă;
• Afișați o serie de operații astfel încât matricea rezultată după efectuarea acestora să aibă un număr cât mai mare de celule nule.

Date de intrare

Inputul conține pe prima linie un număr natural $C$, egal cu $1$ sau $2$, reprezentând cerința care trebuie rezolvată.

Pe următoarea linie se află numerele naturale $N$ și $M$.

Pe fiecare dintre următoarele $N$ linii se află câte $M$ numere întregi separate prin spații.

Date de ieșire

Dacă $C=1$, afișați $\text{DA}$ dacă există o serie de operații astfel încât matricea să devină complet nulă, sau $\text{NU}$ dacă nu există o astfel de serie.

Dacă $C=2$, afișați pe prima linie un număr natural $K$ - numărul de operații folosit, iar pe următoarele $K$ linii afișați operațiile, câte una pe câte o linie, codificate în modul următor: $P_i, x_i, y_i, A_i$, unde $P_i$ este orientarea dorită a lopeții în cea de-a i-a operație (vezi imaginea), $x_i$ și $y_i$ reprezintă colțul cel mai din stânga-sus afectat de operație (vezi imaginea), iar $A_i$ este un număr rațional ce repezintă cantitatea dorită de zăpadă adăugată în fiecare celulă (dacă $A_i$ este negativ atunci de fapt va scădea cantitatea de zăpadă).

Cele 8 orientări posibile, împreună cu pătratul de referință pentru poziție

Restricții și precizări

• $1 \leq C \leq 2$, număr natural;
• $3 \leq N, M \leq 100$, numere naturale;
• inițial, $-1000 \leq V[i][j] \leq 1000$, numere întregi, $\forall 0 \leq i < N, 0 \leq j < M$
• Este posibil ca, în urma efectuării celor $K$ pași, $V[i][j]$ să nu mai fie numere întregi și să nu se mai încadreze în intervalul $[-1000, 1000]$
• $0 \leq K \leq 10^5$, număr natural;
• $0 \leq P_i \leq 7$, numere naturale, $\forall 0 \leq i < K$;
• $0 \leq x_i < N, 0 \leq y_i < M$, numere naturale, $\forall 0 \leq i < K$;
• $-10^9 \leq A_i \leq 10^9$, numere raționale, $\forall 0 \leq i < K$.

Punctare

Pentru cazurile cu $C=2$, concurentul va primi punctajul maxim dacă numărul de celule nule este egal cu maximul posibil. O celulă se consideră nulă dacă valoarea ei absolută este mai mică decât $10^{-6}$. Dacă soluția concurentului obține o matrice cu B elemente nenule, iar minimul posibil este de A elemente nenule, atunci punctajul testului va fi proporțional cu $\frac{2}{2+B-A}$. Exemplu: minimul posibil este $0$ iar concurentul mai are $2$ elemente nenule în matrice, atunci scorul va fi proporțional cu $\frac{2}{2+2-0} = 0,5$

Exemplul 1

stdin

1
3 3
1 1 1
1 0 0
0 0 0

stdout

DA

Explicație

În primul exemplu se poate observa că există un șir de operații (format chiar dintr-o singură operație) pentru ca matricea să devină nulă.

Exemplul 2

stdin

2
3 3
6 6 6
7 1 1
0 0 1

stdout

2
6 0 0 -6
3 1 0 -1

Explicație

Pentru al doilea exemplu, cele două operații vor face matricea nulă.