Gefin er tafla af stærð $n \times n$, þar sem hver af $n^2$ reitum hennar inniheldur eina af tölunum $-1$, $0$ eða $1$. Einnig eru gefnar fjórar heiltölur $A_L, A_D, A_R$ og $A_U$. Við viljum teikna tvær brotalínur:

• eina sem tengir efra vinstra horn töflunnar við neðra hægra hornið; og færist eftir brúnum reitanna eingöngu til hægri og niður,
• og hina sem tengir neðra vinstra horn töflunnar við efra hægra hornið, og færist eingöngu til hægri og upp.

Brotalínurnar tvær skipta töflunni í fjögur (mögulega tóm) svæði: vinstri, niðri, hægri og uppi. Athugaðu hvort til séu tvær brotalínur þannig að summa reitanna á þessum fjórum svæðum sé $A_L, A_D, A_R$ og $A_U$, í sömu röð. Prentaðu TAK (já) eða NIE (nei) fyrir hvert af $t$ óháðu prófunartilvikunum.

Myndirnar sýna sömu $5 \times 5$ töfluna úr sýnidæminu.

Vinstri myndin sýnir skiptingu í svæði með summurnar $(1, 0, -2, 1)$ (í röðinni $A_L, A_D, A_R, A_U$). Fyrri brotalínunni má lýsa með orðinu RDDDRRDRDR, og þeirri síðari með RURUURRUUR (þar sem D, U og R tákna færslur eftir brúnum niður, upp og til hægri, í sömu röð). Til dæmis inniheldur hægra svæðið 8 reiti með summuna $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.

Hægri myndin sýnir skiptingu í svæði með summurnar $(0, 2, -3, 1)$. Vinstra svæðið er tómt, svo summa reita þess er núll. Brotalínunum má lýsa með orðunum DRRRRDDRDD og UUUURURRRR.

Ekki er hægt að skipta sömu töflu í svæði með summurnar $(-2, 0, 1, 1)$, þ.e. $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Athugið að sömu gildi, en í annarri röð, birtast á vinstri myndinni – röðin skiptir máli.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölu $t$ ($1 \le t \le 100\,000$), sem táknar fjölda prófunartilvika.

Fyrsta lína prófunartilviks inniheldur fimm heiltölur $n, A_L, A_D, A_R, A_U$ ($1 \le n \le 2000; -n^2 \le A_L, A_D, A_R, A_U \le n^2$), sem tákna hliðarlengd töflunnar og óskaðar summur svæðanna fjögurra.

Hver af næstu $n$ línum prófunartilviksins lýsir töflunni; $i$-ta línan inniheldur $n$ heiltölur $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), sem lýsa $i$-tu röðinni. Heildarsumma töflunnar er jöfn $A_L + A_D + A_R + A_U$.

Heildarsumma $n^2$ yfir öll prófunartilvik fer ekki yfir $4\,000\,000$.

Úttak

Prentaðu nákvæmlega $t$ línur – fyrir hvert prófunartilvik skaltu prenta orðið TAK (já) ef til eru brotalínur sem skipta töflunni í svæði með tilgreindu summunum, eða orðið NIE (nei) annars.

Dæmi

Inntak

5
5 1 0 -2 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 0 2 -3 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
5 -2 0 1 1
1 0 -1 0 0
1 0 0 1 -1
0 1 -1 0 -1
0 0 0 0 1
-1 0 0 0 0
2 1 -1 0 1
1 0
-1 1
1 0 0 0 0
0

Úttak

TAK
TAK
NIE
NIE
TAK

Athugasemd

Fyrstu þrjú prófunartilvikin samsvara dæmunum sem sýnd eru í verkefnislýsingunni. Þau innihalda sömu töflu og fyrirspurnir um summurnar $(A_L, A_D, A_R, A_U)$ í röð:

1. $(1, 0, -2, 1)$, svar TAK
2. $(0, 2, -3, 1)$, svar TAK
3. $(-2, 0, 1, 1)$, svar NIE