Gegeben ist ein Spielbrett der Größe $n \times n$, wobei jede seiner $n^2$ Zellen eine der Zahlen $-1$, $0$ oder $1$ enthält. Außerdem sind vier ganze Zahlen $A_L, A_D, A_R$ und $A_U$ gegeben. Wir möchten zwei Polygonzüge (Streckenzüge) zeichnen:
- einen, der die obere linke Ecke des Bretts mit der unteren rechten Ecke verbindet und sich entlang der Zellkanten nur nach rechts und nach unten bewegt,
- und einen weiteren, der die untere linke Ecke des Bretts mit der oberen rechten Ecke verbindet und sich nur nach rechts und nach oben bewegt.
Die beiden Polygonzüge teilen das Brett in vier (möglicherweise leere) Bereiche: links, unten, rechts und oben. Prüfe, ob zwei Polygonzüge existieren, sodass die Zellen in diesen vier Bereichen jeweils die Summen $A_L, A_D, A_R$ und $A_U$ ergeben. Gib für jeden der $t$ unabhängigen Testfälle TAK (ja) oder NIE (nein) aus.
Die Abbildungen zeigen dasselbe $5 \times 5$-Brett aus dem Beispieltest.
Die linke Abbildung zeigt eine Aufteilung in Bereiche mit den Summen $(1, 0, -2, 1)$ (in der Reihenfolge $A_L, A_D, A_R, A_U$). Der erste Polygonzug lässt sich durch das Wort RDDDRRDRDR beschreiben, der zweite durch RURUURRUUR (wobei D, U und R Bewegungen entlang der Kanten nach unten, oben bzw. rechts bezeichnen). Beispielsweise enthält der rechte Bereich 8 Zellen mit einer Summe von $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
Die rechte Abbildung zeigt eine Aufteilung in Bereiche mit den Summen $(0, 2, -3, 1)$. Der linke Bereich ist leer, sodass die Summe seiner Zellen null beträgt. Die Polygonzüge lassen sich durch die Wörter DRRRRDDRDD und UUUURURRRR beschreiben.
Dasselbe Brett kann nicht in Bereiche mit den Summen $(-2, 0, 1, 1)$ aufgeteilt werden, d. h. $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Beachte, dass dieselben Werte, jedoch in einer anderen Reihenfolge, in der linken Abbildung auftreten – die Reihenfolge ist entscheidend.
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl $t$ ($1 \le t \le 100\,000$), welche die Anzahl der Testfälle angibt.
Die erste Zeile eines Testfalls enthält fünf ganze Zahlen $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$), welche die Seitenlänge des Bretts und die gewünschten Summen der vier Bereiche bezeichnen.
Jede der nächsten $n$ Zeilen des Testfalls beschreibt das Brett; die $i$-te Zeile enthält $n$ ganze Zahlen $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), welche die $i$-te Zeile beschreiben. Die Gesamtsumme des Bretts ist gleich $A_L + A_D + A_R + A_U$.
Die Gesamtsumme von $n^2$ über alle Testfälle hinweg überschreitet $4\,000\,000$ nicht.
Ausgabe
Gib genau $t$ Zeilen aus – gib für jeden Testfall das Wort TAK (ja) aus, falls Polygonzüge existieren, die das Brett in Bereiche mit den angegebenen Summen teilen, oder andernfalls das Wort NIE (nein).
Beispiel
Eingabe
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
Ausgabe
TAK TAK NIE NIE TAK
Hinweis
Die ersten drei Testfälle entsprechen den in der Aufgabenstellung gezeigten Beispielen. Sie enthalten dasselbe Brett und Abfragen für die Summen $(A_L, A_D, A_R, A_U)$ in folgender Reihenfolge:
- $(1, 0, -2, 1)$, Antwort
TAK - $(0, 2, -3, 1)$, Antwort
TAK - $(-2, 0, 1, 1)$, Antwort
NIE