Case of Chocolate

题意翻译

“安卓”安德里威是银河系大名鼎鼎的侦探。现在他没有调查案子，而是在吃巧克力打发时间。 一块巧克力可以看成一个$n×n$的矩阵，其中每个方格都是一小块巧克力。矩阵的每一纵列从左往右编号为$1$到$n$，而橫行从上往下编号。我们把一条从矩阵的左下角到右上角的对角线称作反对角线。首先安德里威吃了反对角线下方的所有巧克力，然后他对剩下的三角形部分做了$q$个如下的操作：先在反对角线上选定一块巧克力并指定一个方向（左或上），再从这块巧克力开始往指定的方向吃到已经被吃掉的部分或巧克力的边缘位置为止。 每个操作结束后，他想要知道这次他吃了多少块巧克力。 第一行包含两个正整数$n(1<=n<=10^9)$和$q(1<=q<=2×10^5)$，表示巧克力块的尺寸和操作的个数。 接下来$q$行描述操作：第$i$行包含两个表示被选定的巧克力的行和列的整数$x_{i}$和$y_{i}(1<=x_{i},y_{i}<=n,x_{i}+y_{i}=n+1)$以及一个表示指定的方向的字符(L表示左，U表示上)。 输出$q$行，第$q$行表示第$i$个操作吃掉的巧克力。 样例示意图：  同一次操作中被吃掉的巧克力被涂上了同种颜色。反斜线上的巧克力块上有导致这块巧克力被吃掉的操作编号。 第二个样例中安德里威在第五次操作时试图第二次从第$1$行和第$10$列交叉处的方块开始吃，但是这个方块已经被吃掉了，所以他实际上什么也没有吃。 翻译提供者：owogon

题目描述

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.

输入输出格式

输入格式

The first line contains integers $ n $ ( $ 1<=n<=10^{9} $ ) and $ q $ ( $ 1<=q<=2·10^{5} $ ) — 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).

输出格式

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

输入输出样例

输入样例 #1

6 5
3 4 U
6 1 L
2 5 L
1 6 U
4 3 U

输出样例 #1

4
3
2
1
2

输入样例 #2

10 6
2 9 U
10 1 U
1 10 U
8 3 L
10 1 L
6 5 U

输出样例 #2

9
1
10
6
0
2

说明

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.