Du får ett bräde av storlek $n \times n$, där var och en av dess $n^2$ rutor innehåller ett av talen $-1$, $0$ eller $1$. Du får också fyra heltal $A_L, A_D, A_R$ och $A_U$. Vi vill rita två polylinjer:

• en som förbinder brädets övre vänstra hörn med det nedre högra hörnet, och som rör sig längs rutornas kanter endast åt höger och nedåt,
• och en annan som förbinder brädets nedre vänstra hörn med det övre högra hörnet, och som rör sig endast åt höger och uppåt.

De två polylinjerna delar in brädet i fyra (möjligen tomma) regioner: vänster, nere, höger och uppe. Kontrollera om det finns två polylinjer sådana att rutorna i dessa fyra regioner summerar till $A_L, A_D, A_R$ respektive $A_U$. Skriv ut TAK (ja) eller NIE (nej) för vart och ett av de $t$ oberoende testfallen.

Figurerna visar samma $5 \times 5$-bräde från exempeltestet.

Den vänstra figuren visar en uppdelning i regioner med summorna $(1, 0, -2, 1)$ (i ordningen $A_L, A_D, A_R, A_U$). Den första polylinjen kan beskrivas med ordet RDDDRRDRDR, och den andra med RURUURRUUR (där D, U och R betecknar förflyttningar längs kanter nedåt, uppåt respektive åt höger). Till exempel innehåller den högra regionen 8 rutor med summan $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.

Den högra figuren visar en uppdelning i regioner med summorna $(0, 2, -3, 1)$. Den vänstra regionen är tom, så summan av dess rutor är noll. Polylinjerna kan beskrivas med orden DRRRRDDRDD och UUUURURRRR.

Samma bräde kan inte delas in i regioner med summorna $(-2, 0, 1, 1)$, dvs. $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Observera att samma värden, men i en annan ordning, förekommer i den vänstra figuren – ordningen spelar roll.

Indata

Den första raden i indatan innehåller ett enda heltal $t$ ($1 \le t \le 100\,000$), som anger antalet testfall.

Den första raden i ett testfall innehåller fem heltal $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$), som anger sidlängden på brädet och de önskade summorna för de fyra regionerna.

Var och en av de följande $n$ raderna i testfallet beskriver brädet; den $i$:te raden innehåller $n$ heltal $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), som beskriver den $i$:te raden. Den totala summan av brädet är lika med $A_L + A_D + A_R + A_U$.

Den totala summan av $n^2$ över alla testfall överstiger inte $4\,000\,000$.

Utdata

Skriv ut exakt $t$ rader – för varje testfall, skriv ut ordet TAK (ja) om det finns polylinjer som delar in brädet i regioner med de angivna summorna, eller ordet NIE (nej) annars.

Exempel

Indata

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

Utdata

TAK
TAK
NIE
NIE
TAK

Anmärkning

De tre första testfallen motsvarar exemplen som visas i problembeskrivningen. De innehåller samma bräde och frågor för summorna $(A_L, A_D, A_R, A_U)$ i ordning:

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