CF555C.Case of Chocolate

Andrewid the Android is a galaxy-known detective. Now he does not investigate any case and is eating chocolate out of boredom.

A bar of chocolate can be presented as an n × n table, where each cell represents one piece of chocolate. The columns of the table are numbered from 1 to n from left to right and the rows are numbered from top to bottom. Let's call the anti-diagonal to be a diagonal that goes the lower left corner to the upper right corner of the table. First Andrewid eats all the pieces lying below the anti-diagonal. Then he performs the following q actions with the remaining triangular part: first, he chooses a piece on the anti-diagonal and either direction 'up' or 'left', and then he begins to eat all the pieces starting from the selected cell, moving in the selected direction until he reaches the already eaten piece or chocolate bar edge.

After each action, he wants to know how many pieces he ate as a result of this action.

安卓侦探安德鲁伊德是银河系闻名的侦探。如今他没有在调查任何案件，而是百无聊赖地吃着巧克力。

一块巧克力可以表示为一个 $n \times n$ 的方阵，其中每个格子代表一块巧克力。表格的列从左到右编号为 $1$ 到 $n$，行从上到下编号。我们称反对角线为从表格左下角延伸至右上角的对角线。首先，安德鲁伊德吃掉所有位于反对角线下方的巧克力块。接着，他对剩余的三角形部分执行 $q$ 次操作：每次操作中，他先在反对角线上选择一个格子，并选定方向“向上”或“向左”，然后从该格子出发，沿所选方向持续吃掉巧克力块，直到抵达已被吃掉的格子或巧克力方阵的边界为止。

每次操作后，他想知道本次操作共吃掉了多少块巧克力。

The first line contains integers n (1 ≤ n ≤ 109) and q (1 ≤ q ≤ 2·105) — the size of the chocolate bar and the number of actions.

Next q lines contain the descriptions of the actions: the i-th of them contains numbers x__i and y__i (1 ≤ x__i, y__i ≤ n, x__i + y__i = n + 1) — the numbers of the column and row of the chosen cell and the character that represents the direction (L — left, U — up).

第一行包含两个整数 $n$（$1 \leq n \leq 10^9$）和 $q$（$1 \leq q \leq 2 \cdot 10^5$）——分别表示巧克力条的尺寸和操作次数。

接下来 $q$ 行描述各次操作：其中第 $i$ 行包含两个数 $x_i$ 和 $y_i$（$1 \leq x_i, y_i \leq n$，且满足 $x_i + y_i = n + 1$）——分别表示所选单元格的列号与行号，以及表示方向的字符（L 表示向左，U 表示向上）。

Print q lines, the i-th of them should contain the number of eaten pieces as a result of the i-th action.

输出 q 行，其中第 i 行应包含执行第 i 次操作后被吃掉的方块数量。

Pictures to the sample tests:

The pieces that were eaten in the same action are painted the same color. The pieces lying on the anti-diagonal contain the numbers of the action as a result of which these pieces were eaten.

In the second sample test the Andrewid tries to start eating chocolate for the second time during his fifth action, starting from the cell at the intersection of the 10-th column and the 1-st row, but this cell is already empty, so he does not eat anything.

样例测试的图片：

在同一次操作中被吃掉的方块涂成相同颜色。位于副对角线（从右上到左下的对角线）上的方块中所填数字，表示该方块是在第几次操作中被吃掉的。

在第二个样例测试中，Andrewid 尝试在其第五次操作时第二次开始吃巧克力，起始位置为第 1 行、第 10 列的方块；但该方块此时已为空，因此他什么也没有吃到。