La comida de los pollitos
Los pollitos pasan todo el día picoteando el suelo del gallinero para comer los granos que van encontrando. Has estado varios días observando sus movimientos y has descubierto que todos ellos siguen un curioso patrón basado en las baldosas que hay en el suelo. Se despiertan mirando en una dirección (norte, sur, este, oeste) y comienzan a andar en esa dirección siguiendo un movimiento en espiral en el sentido de las agujas del reloj. El paseo termina cuando se cansan (cada pollito tiene un aguante distinto) o en su recorrido se topan con el borde del gallinero, momento en el que quedan aturdidos y se duermen hasta el día siguiente.
Además, en cada baldosa que pisan (incluída la que ocupan al despertarse) miran si hay pienso y si lo hay, comen un grano antes de dar el siguiente paso. Si no hay, simplemente siguen avanzando. Como son pequeños, cuando coinciden en un punto comen al mismo tiempo sin molestarse y a veces incluso duermen en el mismo sitio.
Para conseguir que tus pollitos crezcan lo más rápidamente posible sin gastar de más, has decidido distribuir los granos en el gallinero de forma que en cada paso cada pollito se encuentre un grano y pueda comerlo. Conoces la dirección en que se despiertan los pollitos, y el número de pasos que pueden dar en la espiral antes de cansarse y parar hasta el día siguiente. Ahora debes averiguar los granos que tienes que colocar en cada punto para que, al acabar el día, no quede ninguno y todos los pollitos hayan comido el máximo posible.
Entrada
La entrada comienza con una línea con el número de casos de prueba que deberán procesarse. Cada caso comienza con una línea con tres números, f, c y n indicando, respectivamente, el tamaño del gallinero en la dirección norte-sur, el tamaño en la dirección oeste-este y el número de pollitos (1 ≤ f, c ≤ 50; 0 ≤ n ≤ 500). Las n líneas siguientes contienen la información de cada pollito. El primer número, v, indica la posición en la dirección norte-sur (1 ≤ v ≤ f), el segundo, h, la posición en la dirección oeste-este (1 ≤ h ≤ c), después se indica la dirección en la que empieza a moverse el pollito (N, S, E, W) y finalmente el número máximo de pasos que aguanta antes de dormirse a descansar (al menos uno).
Salida
Para cada caso de prueba se escribirán f líneas. En cada una se escribirán c valores, separados por un espacio en blanco, con el número de granos que hay que poner en cada punto. Tras cada caso de prueba se escribirá una línea con tres guiones (---).
Entrada de ejemplo
2 7 8 3 1 2 E 2 6 3 N 25 4 6 E 21 4 3 2 1 1 N 3 4 2 W 3
Salida de ejemplo
0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 2 2 1 1 1 0 1 1 2 2 1 1 1 0 1 1 2 2 1 1 1 0 1 1 1 1 0 0 0 --- 1 0 0 0 0 0 1 1 0 1 1 0 ---