Se te da un tablero de tamaño $n \times n$, donde cada una de sus $n^2$ celdas contiene uno de los números $-1$, $0$ o $1$. También se te dan cuatro enteros $A_L, A_D, A_R$ y $A_U$. Queremos dibujar dos polilíneas:
- una que conecte la esquina superior izquierda del tablero con la esquina inferior derecha, moviéndose a lo largo de los bordes de las celdas únicamente hacia la derecha y hacia abajo,
- y la otra que conecte la esquina inferior izquierda del tablero con la esquina superior derecha, moviéndose únicamente hacia la derecha y hacia arriba.
Las dos polilíneas dividen el tablero en cuatro regiones (posiblemente vacías): izquierda, abajo, derecha y arriba. Comprueba si existen dos polilíneas tales que las celdas en estas cuatro regiones sumen $A_L, A_D, A_R$ y $A_U$, respectivamente. Imprime TAK (sí) o NIE (no) para cada uno de los $t$ casos de prueba independientes.
Las figuras muestran el mismo tablero de $5 \times 5$ de la prueba de ejemplo.
La figura izquierda muestra una partición en regiones con sumas $(1, 0, -2, 1)$ (en el orden $A_L, A_D, A_R, A_U$). La primera polilínea puede describirse con la palabra RDDDRRDRDR, y la segunda con RURUURRUUR (donde D, U y R denotan movimientos a lo largo de los bordes hacia abajo, hacia arriba y hacia la derecha, respectivamente). Por ejemplo, la región derecha contiene 8 celdas con una suma $A_R = 0 - 1 - 1 + 0 - 1 + 0 + 1 + 0 = -2$.
La figura derecha muestra una partición en regiones con sumas $(0, 2, -3, 1)$. La región izquierda está vacía, por lo que la suma de sus celdas es cero. Las polilíneas pueden describirse con las palabras DRRRRDDRDD y UUUURURRRR.
El mismo tablero no puede particionarse en regiones con sumas $(-2, 0, 1, 1)$, es decir, $A_L = -2, A_D = 0, A_R = 1, A_U = 1$. Observa que los mismos valores, pero en un orden diferente, aparecen en la figura izquierda: el orden importa.
Entrada
La primera línea de la entrada contiene un solo entero $t$ ($1 \le t \le 100\,000$), que denota el número de casos de prueba.
La primera línea de un caso de prueba contiene cinco enteros $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$), que denotan la longitud del lado del tablero y las sumas deseadas de las cuatro regiones.
Cada una de las siguientes $n$ líneas del caso de prueba describe el tablero; la $i$-ésima línea contiene $n$ enteros $a_{i1}, a_{i2}, \dots, a_{in}$ ($a_{ij} \in \{-1, 0, 1\}$), que describen la $i$-ésima fila. La suma total del tablero es igual a $A_L + A_D + A_R + A_U$.
La suma total de $n^2$ en todos los casos de prueba no excede $4\,000\,000$.
Salida
Imprime exactamente $t$ líneas: para cada caso de prueba imprime la palabra TAK (sí) si existen polilíneas que dividan el tablero en regiones con las sumas especificadas, o la palabra NIE (no) en caso contrario.
Ejemplo
Entrada
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
Salida
TAK TAK NIE NIE TAK
Nota
Los primeros tres casos de prueba corresponden a los ejemplos mostrados en el enunciado. Contienen el mismo tablero y consultas para las sumas $(A_L, A_D, A_R, A_U)$ en orden:
- $(1, 0, -2, 1)$, respuesta
TAK - $(0, 2, -3, 1)$, respuesta
TAK - $(-2, 0, 1, 1)$, respuesta
NIE