Minimizing Trapped Cells in a Conveyor Belt Grid

Farmer John’s milk factory is arranged as an (N \times N) grid (with (1 \le N \le 1000)). Each cell in the grid will eventually have a conveyor belt. A cell at position ((a,b)) is located in the (a)th row (from the top) and the (b)th column (from the left). There are five types of cells:

• L — A conveyor belt that sends any object one cell to the left per unit time.
• R — A conveyor belt that sends any object one cell to the right per unit time.
• U — A conveyor belt that sends any object one cell up per unit time.
• D — A conveyor belt that sends any object one cell down per unit time.
• ? — A cell on which no conveyor belt has yet been built.

Note that a conveyor belt may move an object off the grid. A cell (c) is called unusable if and only if, when an object is placed on (c), it will never leave the grid (i.e. it will move forever inside the grid).

Initially, all cells are marked as (\texttt{?}). Then over the next (Q) days (with (1 \le Q \le 2 \cdot 10^5)), on day (i) Farmer John selects a cell that is still (\texttt{?}) and builds a conveyor belt of type (t_i) (where (t_i \in {L, R, U, D})) at that position ((r_i,c_i)). The input guarantees that the chosen cell is always free (i.e. currently (\texttt{?})).

After each day, Farmer John will then optimally choose belt types for every remaining (\texttt{?}) cell in order to minimize the number of unusable cells. An object placed on a free cell (one that is still (\texttt{?})) can be assumed to follow the assignment that leads to an exit if possible. Only cells that already have fixed (built) belt types may force an object to eventually fall into a cycle. In other words, if a fixed cell’s conveyor belt (or chain of fixed belts) forces an object to eventually fall into a cycle, then that cell—and any fixed cell whose unique path leads into that cycle—is considered unusable.

Your task is: after each day, compute the minimum possible number of unusable cells, assuming that the remaining cells (the ones still marked (\texttt{?})) are set optimally.

In more detail, for each fixed cell (a cell on which a belt has been built), let its next cell be the cell reached by moving one unit in the direction indicated by its belt. If that adjacent cell is outside the grid or is still free (marked (\texttt{?})), then an object at the fixed cell can be made safe (by appropriately choosing the belt for the free cell, if needed, or it exits immediately). However, if the fixed cells form a cycle (or a chain that eventually runs into a cycle solely made of fixed cells), then none of those cells can be made safe. Compute the total count of such forced unusable (trapped) cells among the fixed ones after each day.

(\textbf{Note:}) All formulas above are written in (\LaTeX) format.

inputFormat

The first line contains two integers (N) and (Q), denoting the size of the grid and the number of days respectively.\n\nThen (Q) lines follow. The (i)th of these lines contains two integers (r_i) and (c_i) and a character (t_i) (one of L, R, U, D), indicating that on day (i), a belt of type (t_i) is built in cell ((r_i,c_i)) (the grid uses 1-indexing).\n\nIt is guaranteed that every cell is chosen at most once.

outputFormat

Output (Q) lines. The (i)th line should contain a single integer: the minimum possible number of unusable (trapped) cells after day (i), assuming optimal assignments for all remaining free ((\texttt{?})) cells.

sample

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

0
0
0
0