¡Caballos! P81316

¡Los caballos inundan el tablero de ajedrez! Hemos dejado a $k$ de ellos repartidos por un tablero rectangular de tamaño $n\times m$, y te pedimos que calcules, para cada casilla del tablero, de cuántos modos es posible mover cualquiera de los $k$ caballos para llegar a la casilla en exactamente $t$ saltos. (Suponemos que sabes que el caballo es una ficha que hace saltos en forma de L, avanzando dos casillas en una dirección cualquiera y otra en una dirección perpendicular a la anterior. Si tienes cualquier duda, !‘pregunta!).

Por ejemplo, en el tablero siguiente,

el caballo marcado como $C_1$ puede llegar a $X$ en 3 saltos de exactamente 3 modos (dos de ellos, por cierto, ocupando la casilla donde está $C_2$ antes de llegar a $X$). En cambio, el caballo $C_2$ puede llegar a $X$ en 3 saltos de 6 modos distintos (de los 6, en 4 de ellos hace un salto que luego deshace, y a continuación salta a $X$; de los 6, en 2 de ellos pasa por $X$ antes de acabar en $X$: eso está permitido). Por lo tanto, hay $9$ modos de llegar a la casilla $X$.

Te pedimos que calcules el número total de modos de llegar a cada una de las casillas del tablero en $t$ saltos.

Entrada

Cada entrada empieza con el número $0<c\leq 20$ de casos. Cada caso se da en una línea, con los números $n,m\geq 3$, $k>0$ y $t\geq 0$ separados por espacios, y $k$ líneas con las coordenadas iniciales de los $k$ caballos: dos números entre $1$ y $n$ (fila) y entre $1$ y $m$ (columna). Se te garantiza que las dimensiones del tablero $n$ y $m$ no serán mayores de $100$, y que $t$ será menor de $100$. El número $k$ de caballos será inferior a $10000$. Además, podría pasar que varios caballos ocuparan la misma casilla inicial: en tal caso, usar cada uno de ellos contabilizaría como un modo distinto de llegar a la casilla objetivo.

Salida

Para cada caso, escribe $n$ filas de $m$ números cada una, separados por comas, con el número de modos de llegar a la casilla correspondiente. Se entiende que el primer número de la primera fila corresponde a la casilla $(1,1)$, y que el último número de la última fila corresponde a la casilla $(n,m)$. Si el número que debieras escribir es mayor que $10^8$, escribe $>$1e8. Escribe tres guiones --- después de cada caso de pruebas.

Puntuación

Hay 10 entradas. Tu programa recibirá 10 puntos por cada entrada resuelta. Las dimensiones $n$,$m$ de la entrada $i$-ésima no serán mayores de $3, 4, 5, 7, 10, 20, 30, 50, 70, 100$. Además, el número $k$ será $1$ en las primeras 3 entradas, menor que $10$ en las siguientes 3 entradas, y menor que $10000$ en las restantes 4 entradas. Además, el número $t$ será menor que $3,4,5,7$ y $10$ en las primeras 5 entradas, y menor que $100$ en las restantes 5.

Prueba: Final OIE-10
Autor: Omer Giménez