Kunai Trajectories

Ninjas use a weapon called a kunai which is thrown in one of the four cardinal directions. In a plaza arranged as an H × W grid, there are N ninjas standing at the centers of distinct cells. Each ninja holds a kunai and faces either up, down, left, or right. At time \(0\), all ninjas throw their kunais simultaneously toward the direction they are facing.

Each kunai flies at unit speed in its initial direction and remains a point. Whenever at any moment two or more kunais are at the exact same position, they collide and vanish immediately. (Note that collisions occur at the exact time the kunais meet, and a kunai involved in a collision will not continue its motion.) Additionally, since ninjas are very agile, they are never hit by any kunai.

Let \(T\) be a sufficiently large time so that every kunai has either collided with another or has left the plaza. A kunai passes through a cell if at any moment during its flight it is inside that cell. In other words, for a kunai moving horizontally or vertically, the starting cell and every cell entered before it stops (either because of collision or exiting the grid) is counted.

Your task is to calculate how many distinct cells in the grid are passed through by at least one kunai after all motions have terminated.

Collision details and motion:

• Assume the center of the cell at row \(r\) and column \(c\) has coordinates \((c, r)\) (1-indexed).
• The kunai from a ninja at \((x,y)\) with direction
  \(\textbf{R}\): position \((x+t,y)\);
  \(\textbf{L}\): position \((x-t,y)\);
  \(\textbf{U}\): position \((x,y+t)\);
  \(\textbf{D}\): position \((x,y-t)\).
• A collision between two kunais occurs if there exists a time \(t>0\) such that their positions are identical. For example:

• Opposite horizontal: Two kunais in the same row, one moving right and the other left, starting at \((x_i,y)\) and \((x_j,y)\) with \(x_i<x_j\) will collide at time \(t=\frac{x_j-x_i}{2}\).
• Opposite vertical: Two kunais in the same column, one moving up and the other down, starting at \((x,y_i)\) and \((x,y_j)\) with \(y_i<y_j\) will collide at time \(t=\frac{y_j-y_i}{2}\).
• Perpendicular directions: For example, a kunai moving right from \((x_i,y_i)\) and one moving up from \((x_j,y_j)\) will collide if \(x_i+t=x_j\) and \(y_i=y_j+t\), i.e. when \(t=x_j-x_i=y_i-y_j\) (with \(t\ge0\)); similar conditions hold for other perpendicular cases.

Each ninja’s kunai will travel until one of the following happens:

• It collides with another kunai. (If involved in multiple collisions simultaneously, it disappears at the earliest collision time.)
• It exits the plaza. The borders of the grid are at \(x=0.5,\; x=W+0.5,\; y=0.5,\; y=H+0.5\); once the kunai crosses a border, it is no longer on the grid.

The set of cells passed by a kunai thrown in a straight line is easily computed. For a kunai moving horizontally (either right or left) starting from column \(c\), it changes cells each time it crosses a vertical line at \(c\pm0.5, c\pm1.5, \ldots\) (within the grid). Similarly for vertical movement.

For this problem, you are given the grid dimensions and the ninjas’ positions and directions. You must compute the total number of distinct cells that are visited by at least one kunai.

Note on cell counting: Suppose a kunai travels for an effective time \(T\) (which is the minimum of its collision time and its exit time). Then, if it moves horizontally right from column \(c\), the number of cells it passes is \(\lfloor T+0.5\rfloor+1\) (adjusted so that the kunai never goes beyond the grid boundaries). Similarly for other directions.

The formulas for exit times are as follows:

• If moving right: \(T_{exit}=W+0.5-c\).
• If moving left: \(T_{exit}=c-0.5\).
• If moving up: \(T_{exit}=H+0.5-r\).
• If moving down: \(T_{exit}=r-0.5\).

inputFormat

Input Format:

H W N
r₁ c₁ d₁
r₂ c₂ d₂
... (N lines in total)

where:

• \(H\) and \(W\) are the number of rows and columns of the grid, respectively.
• \(N\) is the number of ninjas.
• Each of the next \(N\) lines contains two integers \(r\) and \(c\) (denoting the row and column of a ninja, 1-indexed) and a character \(d\) which is one of U (up), D (down), L (left), or R (right).

outputFormat

Output Format:

X

where \(X\) is the total number of distinct grid cells that are passed through by at least one kunai.

sample

3 3 1
2 2 R

2