Du får et brett med størrelse $n \times n$, der hver av de $n^2$ rutene inneholder ett av tallene $-1$, $0$ eller $1$. Du får også fire heltall $A_L, A_D, A_R$ og $A_U$. Vi ønsker å tegne to polylinjer:
- én som forbinder det øvre venstre hjørnet av brettet med det nedre høyre hjørnet, og som beveger seg langs kantene av rutene kun mot høyre og nedover,
- og en annen som forbinder det nedre venstre hjørnet av brettet med det øvre høyre hjørnet, og som beveger seg kun mot høyre og oppover.
De to polylinjene deler brettet inn i fire (muligens tomme) regioner: venstre, nede, høyre og oppe. Sjekk om det finnes to polylinjer slik at rutene i disse fire regionene summerer til henholdsvis $A_L, A_D, A_R$ og $A_U$. Skriv ut TAK (ja) eller NIE (nei) for hvert av de $t$ uavhengige testtilfellene.
Figurene viser det samme $5 \times 5$-brettet fra eksempeltesten.
Den venstre figuren viser en inndeling i regioner med summene $(1, 0, -2, 1)$ (i rekkefølgen $A_L, A_D, A_R, A_U$). Den første polylinjen kan beskrives med ordet RDDDRRDRDR, og den andre med RURUURRUUR (der D, U og R betegner bevegelser langs kanter henholdsvis nedover, oppover og mot høyre). For eksempel inneholder den høyre regionen 8 ruter med en sum $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
Den høyre figuren viser en inndeling i regioner med summene $(0, 2, -3, 1)$. Den venstre regionen er tom, så summen av rutene i den er null. Polylinjene kan beskrives med ordene DRRRRDDRDD og UUUURURRRR.
Det samme brettet kan ikke deles inn i regioner med summene $(-2, 0, 1, 1)$, dvs. $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Merk at de samme verdiene, men i en annen rekkefølge, vises i den venstre figuren – rekkefølgen har betydning.
Inndata
Den første linjen i inndataene inneholder ett enkelt heltall $t$ ($1 \le t \le 100\,000$), som angir antall testtilfeller.
Den første linjen i et testtilfelle inneholder fem heltall $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$), som angir sidelengden på brettet og de ønskede summene for de fire regionene.
Hver av de neste $n$ linjene i testtilfellet beskriver brettet; den $i$-te linjen inneholder $n$ heltall $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), som beskriver den $i$-te raden. Den totale summen av brettet er lik $A_L + A_D + A_R + A_U$.
Den totale summen av $n^2$ over alle testtilfeller overstiger ikke $4\,000\,000$.
Utdata
Skriv ut nøyaktig $t$ linjer – for hvert testtilfelle skal du skrive ut ordet TAK (ja) hvis det finnes polylinjer som deler brettet inn i regioner med de angitte summene, eller ordet NIE (nei) ellers.
Eksempel
Inndata
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
Utdata
TAK TAK NIE NIE TAK
Merk
De tre første testtilfellene tilsvarer eksemplene som er vist i oppgaveteksten. De inneholder det samme brettet og spørringer etter summene $(A_L, A_D, A_R, A_U)$ i rekkefølge:
- $(1, 0, -2, 1)$, svar
TAK - $(0, 2, -3, 1)$, svar
TAK - $(-2, 0, 1, 1)$, svar
NIE