The chicks spend all day pecking at the floor of the henhouse to eat the grain they find. You’ve been sev- eral days observing their movements and have found that they all follow a curious pattern based on the tiles in the floor. They wake up looking in one di- rection (north, south, east, west) and start walking in that direction following a clockwise spiral move- ment. The ride ends when they get tired (each chick has a different endurance) or run into the edge of the henhouse, where they are stunned and sleep until the next day. For each tile they pass (including the one where they wake up) if there is a grain, they eat it before taking the next step. If there is no grain, they just keep moving forward. Since they are small, when they come together on one point, they eat at the same time without bothering each other and sometimes even sleep in the same place. To get your chicks grow as quickly as possible without overspend, you decided to distribute the grains in the henhouse so that in every step each chick finds a grain and can eat it. You know the direction in which the chicks wake up, and the number of steps they can take in the spiral before getting tired and stop until the next day. Now you must find the grains that you have to place at each point so that, at the end of the day, none is left and all chicks have eaten as much as possible. Input The input begins with the number of test cases to be processed. Each case begins with three numbers, r, c and n meaning, respectively, the size of the chicken coop in the north-south direction, the size in the east-west direction and the number of chicks (1 ≤ r, c ≤ 50; 0 ≤ n ≤ 500). The next n lines contain the chicks information. The first number, v, means the position in the north-south direction (1 ≤ v ≤ r), the second, h, the position in the east-west direction (1 ≤ h ≤ c), next it is the start direction of the chick (N, S, E, W) and finally the maximum number of steps before falling sleep (at least one). Output For each test case r lines are written. In each line c values separated by a blank are written, showing the number of grains needed in each point. After each test case write three scripts (---). Sample Input 2 783 12E2 6 3 N 25 4 6 E 21 432 11N3 42W3
2/2 Sample Output 01100000 00111000 00011111 01122111 01122111 01122111 01111000 --- 100 000 110 110 ---