Anda diberikan sebuah papan berukuran $n \times n$, dengan masing-masing dari $n^2$ selnya berisi salah satu dari bilangan $-1$, $0$, atau $1$. Anda juga diberikan empat bilangan bulat $A_L, A_D, A_R$, dan $A_U$. Kita ingin menggambar dua garis poligonal (polyline):

• satu garis menghubungkan sudut kiri atas papan dengan sudut kanan bawah; bergerak sepanjang tepi sel hanya ke kanan dan ke bawah,
• dan garis lainnya menghubungkan sudut kiri bawah papan dengan sudut kanan atas, bergerak hanya ke kanan dan ke atas.

Kedua garis poligonal tersebut membagi papan menjadi empat wilayah (yang mungkin kosong): kiri, bawah, kanan, dan atas. Periksalah apakah terdapat dua garis poligonal sedemikian sehingga sel-sel di keempat wilayah ini masing-masing berjumlah $A_L, A_D, A_R$, dan $A_U$. Cetak TAK (ya) atau NIE (tidak) untuk masing-masing dari $t$ kasus uji independen.

Gambar di atas menunjukkan papan $5 \times 5$ yang sama dari uji contoh.

Gambar kiri menunjukkan partisi menjadi wilayah-wilayah dengan jumlah $(1, 0, -2, 1)$ (dalam urutan $A_L, A_D, A_R, A_U$). Garis poligonal pertama dapat dideskripsikan dengan kata RDDDRRDRDR, dan yang kedua dengan RURUURRUUR (di mana D, U, dan R masing-masing menyatakan gerakan sepanjang tepi ke bawah, ke atas, dan ke kanan). Sebagai contoh, wilayah kanan berisi 8 sel dengan jumlah $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.

Gambar kanan menunjukkan partisi menjadi wilayah-wilayah dengan jumlah $(0, 2, -3, 1)$. Wilayah kiri kosong, sehingga jumlah sel-selnya adalah nol. Garis-garis poligonal tersebut dapat dideskripsikan dengan kata DRRRRDDRDD dan UUUURURRRR.

Papan yang sama tidak dapat dipartisi menjadi wilayah-wilayah dengan jumlah $(-2, 0, 1, 1)$, yaitu $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Perhatikan bahwa nilai-nilai yang sama namun dengan urutan berbeda muncul pada gambar kiri – urutan sangat berpengaruh.

Masukan

Baris pertama masukan berisi satu bilangan bulat $t$ ($1 \le t \le 100\,000$), yang menyatakan jumlah kasus uji.

Baris pertama dari setiap kasus uji berisi lima bilangan bulat $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$), yang menyatakan panjang sisi papan dan jumlah yang diinginkan dari keempat wilayah.

Masing-masing dari $n$ baris berikutnya pada kasus uji mendeskripsikan papan; baris ke-$i$ berisi $n$ bilangan bulat $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), yang mendeskripsikan baris ke-$i$. Jumlah total seluruh papan sama dengan $A_L + A_D + A_R + A_U$.

Jumlah total $n^2$ di seluruh kasus uji tidak melebihi $4\,000\,000$.

Keluaran

Keluarkan tepat $t$ baris – untuk setiap kasus uji keluarkan kata TAK (ya) jika terdapat garis poligonal yang membagi papan menjadi wilayah-wilayah dengan jumlah yang ditentukan, atau kata NIE (tidak) jika sebaliknya.

Contoh

Masukan

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

Keluaran

TAK
TAK
NIE
NIE
TAK

Catatan

Tiga kasus uji pertama bersesuaian dengan contoh yang ditunjukkan pada deskripsi soal. Ketiganya berisi papan yang sama dan kueri untuk jumlah $(A_L, A_D, A_R, A_U)$ secara berurutan:

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