AlgolympContest | B - Jalali

Cerință

Se dă o matrice, se pot alege de câte ori se vrea două celule adiacente pe una dintre cele $4$ direcții și să se scadă din acestea un număr întreg la alegere. Se poate obține o matrice plină cu valori de $0$?

Date de intrare

Pe prima linie se găsesc două numere, $N$ și $M$ specificând dimensiunea matricii. Pe următoarele linii se află matricea.

Date de ieșire

Pe prima linie se va găsi un singur text cu mesajul $"DA"$ sau $"NU"$, dacă se poate sau nu ajunge la o matrice plină cu valori de $0$.

Restricții și precizări

• $1 \leq N, M \leq 1000$
• $-10^9 \leq A_{i,j} \leq 10^9$
• După efectuarea unei operații este permis să existe elemente negatvie în matrice chiar dacă nu au existat inițial
• Mesaje precum "Da", "nU", "da" ... sunt considerate greșite.

Exemplul 1

stdin

2 3
0 1 2
-1 -1 1

stdout

DA

Explicație

Se pot alege căsuțele $(2,1), (2,2)$ și să se scadă din ele $-1$.
După care să se aleagă elementele $(1,2), (1,3)$ și să se scadă din ele $1$.
În final dacă se aleg elementele $(1,3), (2,3)$, și se scada din ele $1$, obținem o matrice plină cu $0$-uri.

Exemplul 2

stdin

2 2
0 1
0 -1

stdout

NU

Explicație

Nu există nicio succesiune de mutări.