Sinulle annetaan $n \times n$ -kokoinen lauta, jonka jokaisessa $n^2$ ruudussa on yksi luvuista $-1$, $0$ tai $1$. Lisäksi annetaan neljä kokonaislukua $A_L, A_D, A_R$ ja $A_U$. Haluamme piirtää kaksi murtoviivaa:
- yhden, joka yhdistää laudan vasemman yläkulman ja oikean alakulman kulkien ruutujen reunoja pitkin vain oikealle ja alas,
- ja toisen, joka yhdistää laudan vasemman alakulman ja oikean yläkulman kulkien vain oikealle ja ylös.
Nämä kaksi murtoviivaa jakavat laudan neljään (mahdollisesti tyhjään) alueeseen: vasen, ala, oikea ja ylä. Tarkista, onko olemassa kahta murtoviivaa siten, että näiden neljän alueen ruutujen summat ovat vastaavasti $A_L, A_D, A_R$ ja $A_U$. Tulosta TAK (kyllä) tai NIE (ei) jokaiselle $t$ riippumattomasta testitapauksesta.
Kuvat esittävät samaa esimerkkitestin $5 \times 5$ -lautaa.
Vasemmanpuoleinen kuva esittää jakoa alueisiin, joiden summat ovat $(1, 0, -2, 1)$ (järjestyksessä $A_L, A_D, A_R, A_U$). Ensimmäinen murtoviiva voidaan kuvata sanalla RDDDRRDRDR ja toinen sanalla RURUURRUUR (missä D, U ja R tarkoittavat siirtymiä reunoja pitkin alas, ylös ja oikealle). Esimerkiksi oikeanpuoleinen alue sisältää 8 ruutua, joiden summa on $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
Oikeanpuoleinen kuva esittää jakoa alueisiin, joiden summat ovat $(0, 2, -3, 1)$. Vasen alue on tyhjä, joten sen ruutujen summa on nolla. Murtoviivat voidaan kuvata sanoilla DRRRRDDRDD ja UUUURURRRR.
Samaa lautaa ei voida jakaa alueisiin, joiden summat ovat $(-2, 0, 1, 1)$, eli $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Huomaa, että samat arvot, mutta eri järjestyksessä, esiintyvät vasemmanpuoleisessa kuvassa – järjestyksellä on väliä.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $t$ ($1 \le t \le 100\,000$), joka ilmaisee testitapausten lukumäärän.
Testitapauksen ensimmäinen rivi sisältää viisi kokonaislukua $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$), jotka ilmaisevat laudan sivun pituuden sekä neljän alueen halutut summat.
Jokainen testitapauksen seuraavista $n$ rivistä kuvaa lautaa; $i$:s rivi sisältää $n$ kokonaislukua $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), jotka kuvaavat $i$:ttä riviä. Laudan kokonaissumma on yhtä suuri kuin $A_L + A_D + A_R + A_U$.
Lukujen $n^2$ kokonaissumma yli kaikkien testitapausten on enintään $4\,000\,000$.
Tuloste
Tulosta täsmälleen $t$ riviä – tulosta jokaiselle testitapaukselle sana TAK (kyllä), jos on olemassa murtoviivat, jotka jakavat laudan annettujen summien mukaisiin alueisiin, tai muuten sana NIE (ei).
Esimerkki
Syöte
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
Tuloste
TAK TAK NIE NIE TAK
Huomautus
Kolme ensimmäistä testitapausta vastaavat tehtävänannossa näytettyjä esimerkkejä. Ne sisältävät saman laudan ja kyselyt summille $(A_L, A_D, A_R, A_U)$ järjestyksessä:
- $(1, 0, -2, 1)$, vastaus
TAK - $(0, 2, -3, 1)$, vastaus
TAK - $(-2, 0, 1, 1)$, vastaus
NIE