← 返回题目列表

Codeforces · 555/C

C. 巧克力盒

中文机器翻译题面 查看原题

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 行交叉点的单元格开始,但该单元格已经空了,因此他没有吃任何东西。