Android 安德鲁是银河系知名的侦探。现在他不调查任何案件,只是无聊地吃巧克力。
一块巧克力可以呈现为一个 n × n 表,其中每个单元格代表一块巧克力。表的列从左到右编号为 1 到 n,行从上到下编号。我们将反对角线称为从表格的左下角到右上角的对角线。首先,安德鲁德吃掉了反对角线以下的所有棋子。然后他对剩余的三角形部分执行以下 q 动作:首先,他选择反对角线上的一块,并且方向为“向上”或“向左”,然后他开始吃掉从所选单元格开始的所有块,沿着所选方向移动,直到到达已经吃掉的块或巧克力块边缘。
每次行动后,他想知道这次行动他吃了多少块。
输入
第一行包含整数 n (1 ≤ n ≤ 109) 和 q (1 ≤ q ≤ 2·105) — 巧克力棒的大小和动作的数量。
接下来 q 行包含操作的描述:其中第 i 行包含数字 xi 和 yi (1 ≤ xi, yi ≤ n, xi + yi = n + 1) — 所选单元格的列数和行数以及代表方向的字符(L — 向左,U — 向上)。
输出
打印q行,其中第i行应该包含第i个动作所吃掉的棋子的数量。
示例
输入 #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
注意
示例测试图片:
在同一动作中吃掉的棋子被涂成相同的颜色。位于对角线上的棋子包含了导致这些棋子被吃掉的动作的编号。
在第二个样本测试中,Andrewid 尝试在第五次操作中第二次开始吃巧克力,从第 10 列和第 1 行交叉点的单元格开始,但该单元格已经空了,因此他没有吃任何东西。