On vous donne une grille de taille $n \times n$, dont chacune des $n^2$ cases contient l'un des nombres $-1$, $0$ ou $1$. On vous donne également quatre entiers $A_L, A_D, A_R$ et $A_U$. Nous voulons tracer deux lignes brisées :
- l'une reliant le coin supérieur gauche de la grille au coin inférieur droit, en se déplaçant le long des bords des cases uniquement vers la droite et vers le bas,
- et l'autre reliant le coin inférieur gauche de la grille au coin supérieur droit, en se déplaçant uniquement vers la droite et vers le haut.
Les deux lignes brisées divisent la grille en quatre régions (éventuellement vides) : gauche, bas, droite et haut. Vérifiez s'il existe deux lignes brisées telles que les sommes des cases dans ces quatre régions soient respectivement égales à $A_L, A_D, A_R$ et $A_U$. Affichez TAK (oui) ou NIE (non) pour chacun des $t$ cas de test indépendants.
Les figures montrent la même grille $5 \times 5$ issue de l'exemple.
La figure de gauche montre une partition en régions de sommes $(1, 0, -2, 1)$ (dans l'ordre $A_L, A_D, A_R, A_U$). La première ligne brisée peut être décrite par le mot RDDDRRDRDR, et la seconde par RURUURRUUR (où D, U et R désignent respectivement des déplacements le long des bords vers le bas, le haut et la droite). Par exemple, la région de droite contient 8 cases dont la somme vaut $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
La figure de droite montre une partition en régions de sommes $(0, 2, -3, 1)$. La région de gauche est vide, donc la somme de ses cases est nulle. Les lignes brisées peuvent être décrites par les mots DRRRRDDRDD et UUUURURRRR.
La même grille ne peut pas être partitionnée en régions de sommes $(-2, 0, 1, 1)$, c'est-à-dire $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Notez que les mêmes valeurs, mais dans un ordre différent, apparaissent sur la figure de gauche : l'ordre compte.
Entrée
La première ligne de l'entrée contient un seul entier $t$ ($1 \le t \le 100\,000$), désignant le nombre de cas de test.
La première ligne d'un cas de test contient cinq entiers $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$), désignant la longueur du côté de la grille et les sommes souhaitées des quatre régions.
Chacune des $n$ lignes suivantes du cas de test décrit la grille ; la $i$-ème ligne contient $n$ entiers $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), décrivant la $i$-ème ligne de la grille. La somme totale de la grille est égale à $A_L + A_D + A_R + A_U$.
La somme totale de $n^2$ sur l'ensemble des cas de test ne dépasse pas $4\,000\,000$.
Sortie
Affichez exactement $t$ lignes – pour chaque cas de test, affichez le mot TAK (oui) s'il existe des lignes brisées divisant la grille en régions ayant les sommes spécifiées, ou le mot NIE (non) sinon.
Exemple
Entrée
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
Sortie
TAK TAK NIE NIE TAK
Note
Les trois premiers cas de test correspondent aux exemples présentés dans l'énoncé. Ils contiennent la même grille et des requêtes pour les sommes $(A_L, A_D, A_R, A_U)$ dans l'ordre :
- $(1, 0, -2, 1)$, réponse
TAK - $(0, 2, -3, 1)$, réponse
TAK - $(-2, 0, 1, 1)$, réponse
NIE