Dana jest plansza o wymiarach $n \times n$, w której każde z jej $n^2$ pól zawiera jedną z liczb $-1$, $0$ lub $1$. Dane są także cztery liczby całkowite $A_L, A_D, A_R$ oraz $A_U$. Chcemy narysować dwie łamane:
- jedną łączącą lewy górny róg planszy z prawym dolnym rogiem; poruszającą się wzdłuż krawędzi pól wyłącznie w prawo i w dół,
- oraz drugą łączącą lewy dolny róg planszy z prawym górnym rogiem, poruszającą się wyłącznie w prawo i w górę.
Te dwie łamane dzielą planszę na cztery (być może puste) obszary: lewy, dolny, prawy i górny. Sprawdź, czy istnieją dwie łamane takie, że liczby w polach tych czterech obszarów sumują się odpowiednio do $A_L, A_D, A_R$ oraz $A_U$. Wypisz TAK lub NIE dla każdego z $t$ niezależnych przypadków testowych.
Rysunki przedstawiają tę samą planszę $5 \times 5$ z testu przykładowego.
Rysunek po lewej przedstawia podział na obszary o sumach $(1, 0, -2, 1)$ (w kolejności $A_L, A_D, A_R, A_U$). Pierwszą łamaną można opisać słowem RDDDRRDRDR, a drugą słowem RURUURRUUR (gdzie D, U oraz R oznaczają ruchy wzdłuż krawędzi odpowiednio w dół, w górę i w prawo). Na przykład prawy obszar zawiera 8 pól o sumie $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
Rysunek po prawej przedstawia podział na obszary o sumach $(0, 2, -3, 1)$. Lewy obszar jest pusty, więc suma jego pól wynosi zero. Łamane można opisać słowami DRRRRDDRDD oraz UUUURURRRR.
Tej samej planszy nie da się podzielić na obszary o sumach $(-2, 0, 1, 1)$, tj. $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Zauważ, że te same wartości, ale w innej kolejności, pojawiają się na rysunku po lewej – kolejność ma znaczenie.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 100\,000$), oznaczającą liczbę przypadków testowych.
Pierwszy wiersz przypadku testowego zawiera pięć liczb całkowitych $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$), oznaczających długość boku planszy oraz pożądane sumy czterech obszarów.
Każdy z kolejnych $n$ wierszy przypadku testowego opisuje planszę; $i$-ty wiersz zawiera $n$ liczb całkowitych $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), opisujących $i$-ty wiersz planszy. Całkowita suma wszystkich pól planszy jest równa $A_L + A_D + A_R + A_U$.
Łączna suma $n^2$ po wszystkich przypadkach testowych nie przekracza $4\,000\,000$.
Wyjście
Wypisz dokładnie $t$ wierszy – dla każdego przypadku testowego wypisz słowo TAK (tak), jeśli istnieją łamane dzielące planszę na obszary o podanych sumach, lub słowo NIE (nie) w przeciwnym razie.
Przykład
Wejście
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
Wyjście
TAK TAK NIE NIE TAK
Uwaga
Pierwsze trzy przypadki testowe odpowiadają przykładom pokazanym w treści zadania. Zawierają tę samą planszę oraz zapytania o sumy $(A_L, A_D, A_R, A_U)$ kolejno:
- $(1, 0, -2, 1)$, odpowiedź
TAK - $(0, 2, -3, 1)$, odpowiedź
TAK - $(-2, 0, 1, 1)$, odpowiedź
NIE