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 ~N~ ninjas in a grid of squares with ~W~ columns and ~H~ rows. Every ninja is in the center of a square, and no two ninjas share the same square. Each ninja has a kunai, and looks toward one of the four directions; up, down, left, or right. At time ~0~, every ninja threw his/her kunai to the direction he/she is looking toward.
Every kunai proceeds straight with speed ~1~. If more than one kunais come to the same place at the same time, they clash each other and disappear. The size of a kunai is so small that we can ignore it. Also, since ninjas can move quickly, they will not be hit by kunais. Each kunai continues to proceed along its direction without losing its speed unless it is clashed with another kunai.
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.
Count the number of squares in the ~W \times H~ grid where kunais pass through after a sufficient amount of time passed.
|~1 \le N \le 100\,000~||The number of ninjas|
|~1 \le W \le 1\,000\,000\,000~, ~1 \le H \le 1\,000\,000\,000~||The size of the grid|
|~1 \le X_i \le W, 1 \le Y_i \le H~||The coordinates of ninjas|
Read the following data from the standard input.
- The first line of input contains two space separated integers ~W~, ~H~, which describe the size of the grid.
- The second line of input contains an integer ~N~, the number of ninjas.
- The ~i~-th line ~(1 \le i \le N)~ of the following ~N~ lines contains three space separated integers ~X_i~, ~Y_i~, ~D_i~, describing that the position of the ninja ~i~ is in the ~X_i~-th column from left and ~Y_i~-th row from above. No two ninjas share the same position. The direction of the ninja ~i~ is described by the value of ~D_i~. – When ~D_i = 0~, the ninja ~i~ is looking toward the right. – When ~D_i = 1~, the ninja ~i~ is looking toward the up. – When ~D_i = 2~, the ninja ~i~ is looking toward the left. – When ~D_i = 3~, the ninja ~i~ is looking toward the down.
Output the number of squares in the ~W \times H~ grid where kunais pass through after a sufficient amount of time passed to the standard output.
In test cases worth ~10\%~ of the full score, ~N \le 1\,000~, ~W \le 1\,000~, ~H \le 1\,000~.
In test cases worth ~40\%~ of the full score, ~N \le 1\,000~.
Sample Input 1
5 4 5 3 3 2 3 2 0 4 2 2 5 4 1 1 1 3
Sample Output 1
Explanation for Sample Output 1
In this example, the grid at time ~0~ is described as follows.
The kunai thrown by the ninja ~i~ is denoted by the kunai ~i~. At time ~0.5~, the kunai ~2~ and the kunai ~3~ will clash each other and disappear. The following figure describes the grid at time ~1~. Here gray squares denote the squares where kunais already passed through.
At time ~2~, the kunai ~1~ and the kunai ~5~ will clash each other and disappear. The grid at time ~2~ is described as follows.
No more kunais are clashed in a square after time ~2~. The grid after a sufficient amount of time passed is described as follows.
Finally, the number of squares in the grid where kunais pass through is ~11~. Therefore, we should output ~11~.
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