Kunai is an acuate weapon used by ninjas whose shape is similar to a knife. Ninjas were attacking their enemies by throwing kunais against them.
There are
Every kunai proceeds straight with speed
In the following figures, the arrows represent kunais. The direction of an arrow describes the direction of a kunai. In these figures, all thick arrows will clash.
On the other hand, in each of the following figures, a thick arrow will not clash with another thick arrow. In the second and the third figure, a thin arrow clashes with a thick arrow. Because clashed arrows will disappear, a thick arrow will not clash with another thick arrow in each of these figures.
Task
Count the number of squares in the
Constraints
|
The number of ninjas |
|
The size of the grid |
|
The coordinates of ninjas |
Input Specification
Read the following data from the standard input.
- The first line of input contains two space separated integers
, , which describe the size of the grid. - The second line of input contains an integer
, the number of ninjas. - The
-th line of the following lines contains three space separated integers , , , describing that the position of the ninja is in the -th column from left and -th row from above. No two ninjas share the same position. The direction of the ninja is described by the value of . – When , the ninja is looking toward the right. – When , the ninja is looking toward the up. – When , the ninja is looking toward the left. – When , the ninja is looking toward the down.
Output Specification
Output the number of squares in the
Grading
In test cases worth
In test cases worth
Sample Input 1
5 4
5
3 3 2
3 2 0
4 2 2
5 4 1
1 1 3
Sample Output 1
11
Explanation for Sample Output 1
In this example, the grid at time
The kunai thrown by the ninja
At time
No more kunais are clashed in a square after time
Finally, the number of squares in the grid where kunais pass through is
Sample Input 2
7 6
12
3 2 3
6 3 2
7 1 3
1 5 0
3 6 1
6 6 1
4 5 2
1 3 0
6 5 2
5 1 2
6 4 3
4 1 3
Sample Output 2
29
Comments