Ti viene data una scacchiera di dimensioni $n \times n$, in cui ciascuna delle sue $n^2$ celle contiene uno dei numeri $-1$, $0$ oppure $1$. Ti vengono inoltre dati quattro interi $A_L, A_D, A_R$ e $A_U$. Vogliamo tracciare due poligonali (spezzate):
- una che colleghi l'angolo superiore sinistro della scacchiera con l'angolo inferiore destro, muovendosi lungo i bordi delle celle solo verso destra e verso il basso,
- e l'altra che colleghi l'angolo inferiore sinistro della scacchiera con l'angolo superiore destro, muovendosi solo verso destra e verso l'alto.
Le due poligonali dividono la scacchiera in quattro regioni (eventualmente vuote): sinistra, basso, destra e alto. Verifica se esistono due poligonali tali che la somma delle celle in queste quattro regioni sia rispettivamente pari a $A_L, A_D, A_R$ e $A_U$. Stampa TAK (sì) oppure NIE (no) per ciascuno dei $t$ casi di test indipendenti.
Le figure mostrano la stessa scacchiera $5 \times 5$ del test di esempio.
La figura a sinistra mostra una partizione in regioni con somme $(1, 0, -2, 1)$ (nell'ordine $A_L, A_D, A_R, A_U$). La prima poligonale può essere descritta dalla parola RDDDRRDRDR, e la seconda da RURUURRUUR (dove D, U e R indicano rispettivamente movimenti lungo i bordi verso il basso, verso l'alto e verso destra). Ad esempio, la regione di destra contiene 8 celle con somma $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
La figura a destra mostra una partizione in regioni con somme $(0, 2, -3, 1)$. La regione di sinistra è vuota, quindi la somma delle sue celle è zero. Le poligonali possono essere descritte dalle parole DRRRRDDRDD e UUUURURRRR.
La stessa scacchiera non può essere partizionata in regioni con somme $(-2, 0, 1, 1)$, cioè $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Nota che gli stessi valori, ma in un ordine diverso, compaiono nella figura a sinistra: l'ordine è importante.
Input
La prima riga dell'input contiene un singolo intero $t$ ($1 \le t \le 100\,000$), che indica il numero di casi di test.
La prima riga di un caso di test contiene cinque interi $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$), che indicano la lunghezza del lato della scacchiera e le somme desiderate delle quattro regioni.
Ciascuna delle successive $n$ righe del caso di test descrive la scacchiera; la $i$-esima riga contiene $n$ interi $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), che descrivono la $i$-esima riga. La somma totale della scacchiera è uguale a $A_L + A_D + A_R + A_U$.
La somma totale di $n^2$ su tutti i casi di test non supera $4\,000\,000$.
Output
Stampa esattamente $t$ righe – per ogni caso di test stampa la parola TAK (sì) se esistono poligonali che dividono la scacchiera in regioni con le somme specificate, oppure la parola NIE (no) altrimenti.
Esempio
Input
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
Output
TAK TAK NIE NIE TAK
Note
I primi tre casi di test corrispondono agli esempi mostrati nel testo. Contengono la stessa scacchiera e query per le somme $(A_L, A_D, A_R, A_U)$ nell'ordine:
- $(1, 0, -2, 1)$, risposta
TAK - $(0, 2, -3, 1)$, risposta
TAK - $(-2, 0, 1, 1)$, risposta
NIE