2D Conveyor Belt

문제

Farmer John's milk factory can be described by an $NN$ by $NN$ ($1\le N\le 10001\; \backslash le\; N\; \backslash le\; 1000$) grid of cells that contain conveyor belts. Position ($a,ba,b$) describes the cell that is in the $aa$-th row from the top and $bb$-th column from the left. There are $55$ types of cells:

1. "L" — the cell is a leftward facing conveyor belt which moves all items on it 1 cell left every time unit.
2. "R" — the cell is a rightward facing conveyor belt which moves all items on it 1 cell right every time unit.
3. "U" — the cell is an upward facing conveyor belt which moves all items on it 1 cell up every time unit.
4. "D" — the cell is a downward facing conveyor belt which moves all items on it 1 cell down every time unit.
5. "?" — Farmer John has not built a conveyor belt at that cell yet.

Note that conveyor belts can also move items outside the grid. A cell $cc$ is unusable if an item placed at cell $cc$ will never exit the conveyor belt grid (i.e. it will move around in the grid forever).

Initially, Farmer John has not started building the factory so all cells start out as "?". For the next $QQ$ ($1\le Q\le 2\cdot {10}^{5}1\; \backslash le\; Q\; \backslash le\; 2\; \backslash cdot\; 10^5$) days starting from day $11$ and ending at day $QQ$, Farmer John will choose a cell that does not have a conveyor belt and build a conveyor belt at the cell.

Specifically, during the $ii$-th day, Farmer John will build a conveyor belt of type $t_{i}t\_i$ ($t_i\in \text{L,R,U,D}t\_i\; \backslash in\; \{\backslash text\{\{L,R,U,D\}\}\}$) at position ($r_i,c_{i}r\_i,c\_i$) ($1\le r_i,c_i\le N1\; \backslash le\; r\_i,c\_i\; \backslash le\; N$). It is guaranteed that there is no conveyor belt at position ($r_i,c_{i}r\_i,c\_i$).

After each day, help Farmer John find the minimum number of unusable cells he can achieve by optimally building conveyor belts on all remaining cells without a conveyor belt.

입력

The first line contains $NN$ and $QQ$.

The $ii$-th of the next $QQ$ lines contains $r_{i}r\_i$, $c_{i}c\_i$, and $t_{i}t\_i$ in that order.

출력

$QQ$ lines, the $ii$-th of which describing the minimum number of unusable cells if Farmer John fills optimally builds conveyor belts on all remaining cells that do not currently have a conveyor belt.

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

0
0
0
2
3

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

0
2
2
4
4
6
6
9

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

0
0
0
0
0
0
0
0
11
11
11
11
13