Na stolu je pričvršcen lavirint sa lopticom u njemu, tako da ga je moguće nagnuti samo na dole ili na desno, odnosno loptica može ici samo u smerovima dole i desno. Za datu poziciju u lavirintu proveriti da li je moguce doći do donjeg desnog polja u lavirintu.

Ulaz

Sa standardnog ulaza se učitava broj $n , a zatim i n² polja, svako polje ima vrednost 0/1, loptica se može kretati samo poljima sa vrednošću 1. Zatim se učitava 5 upita tipa ab gde su a i b brojevi iz intervala [0, n − 1].

Izlaz

Za svaki od 5 upita ispisati “DA” ili “NE” kao oznaku da li se od polja a, b može dozvoljenim kretanjem stići do polja n − 1, n − 1.

Primer

Ulaz

4
1 1 0 0
1 1 1 1
1 1 0 1
1 1 0 1
0 0
1 1
3 1
2 0
2 3

Izlaz

DA
DA
NE
NE
DA