Емил игра компјутерска игра на која има мала матрица со R редови и C колони. Секој елемент во оваа матрица е број кој е еднаков или на 1, или на 0. За да помине во следното ниво, Емил треба да почне од одредено поле (по сопствен избор) на кое што има запишано 1 (единица), и потоа во секој чекор да скокне до друго поле на кое што има 1, и така се додека не се изминат сите полиња со вредноста 1. Не е дозволен скок на поле на кое што има вредност 0 (нула), или на поле кое е веќе посетено. Дали е возможно да се поминат сите полиња со вредност 1, доколку ги имаме следниве две дополнителни ограничувања:

    1) За секој непарен потег/скок (првиот, третиот, петтиот, итн), дозволен е скок само до поле во истиот ред
    2) За секој парен потег/скок (вториот, четвртиот, шестиот, итн), дозволен е скок само до поле во истата колона

Со други зборови, ако почнеме од некое поле A, следното поле B треба да е во истиот ред како и А (бидејќи првиот скок треба да е до поле во истиот ред), понатаму следното поле C треба да е во истата колона како B (бидејќи вториот скок треба да е до поле во иста колона) - и така натаму наизменично (ред, колона, ред, колона, ...).

Напишете програма која ќе отпечати “DA” или “NE”, зависно од тоа дали Емил може да ги помине сите единици од матрицата.

Влез

Во првиот ред се дадени два цели броја R (1 <= R <= 4) и C (1 <= C <= 5), кои што ги означуваат бројот на редови и колони од кои е составена матрицата.

Во секој од следните R редови се запишани по C цели броеви (1 или 0) кои ја дефинираат матрицата.

Излез

Единствената линија од излезот треба да содржи “DA” (доколку може да се поминат сите полиња со 1, користејќи ја постапката означена погоре), или “NE” (доколку не може).

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
2 3
1 0 0
1 1 0

излез
DA

влез
3 3
1 1 1
1 1 1
1 1 1

излез
NE

влез
3 5
1 1 0 1 1
1 1 0 1 1
0 1 0 1 0

излез
DA

Објаснување за првиот тест пример: Може да се почне од втората колона во вториот ред, па да се скокне налево (прв скок), па нагоре (втор скок).

Објаснување за третиот тест пример: Може да се почне од единицата која што се наоѓа во првиот ред втора колона (па скок налево, па надоле, па надесно, па надоле, па надесно, па нагоре, па надесно, па нагоре, па налево).