Description

Farmer John 的牛奶工厂可以用一个 N×N（1≤N≤1000）的方阵来表示，其中的方格带有传送带。

位置 (a,b)描述了位于从上往下第 a 行、从左往右第 b 列的方格。有 5种类型的方格：

"L" — 该方格是一个向左的传送带，每一单位时间会将所有物品向左移动一格。

"R" — 该方格是一个向右的传送带，每一单位时间会将所有物品向右移动一格。

"U" — 该方格是一个向上的传送带，每一单位时间会将所有物品向上移动一格。

"D" — 该方格是一个向下的传送带，每一单位时间会将所有物品向下移动一格。

"?" — Farmer John 还没有在该方格上建造传送带。

注意传送带也可以将物品移动到方阵外。一个方格 c 是不可用的，如果一个放置在方格 c 上的物品将永远不会离开传送带方阵（即它会永远在方阵中移动）。

初始时，Farmer John 还没有开始建造工厂，所以所有方格都以 "?" 开始。接下来的 Q（1≤Q≤2⋅1e5）天，从第 1 天开始到第 Q 天，Farmer John 将选择一个没有传送带的方阵并在该方阵上建造一个传送带。

具体地说，在第 i 天，Farmer John 将在位置 (ri,ci)（1≤ri,ci≤N）建造一个类型 ti（ti∈{L,R,U,D}）的传送带。输入保证在位置 (ri,ci) 没有传送带。

每天过后，请帮助 Farmer John 求出他通过最优地在所有余下的没有传送带的方格上建造传送带可以达到的不可用方格的最小数量。

Format

Input

输入的第一行包含 N 和 Q。 以下 Q 行，第 i 行依次包含 ri，ci 和 ti

Output

输出 Q 行，每行包含 Farmer John 最优地在所有余下的没有传送带的方格上建造传送带时不可用方格的最小数量。

Samples

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

0
0
0
2
3

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

0
2
2
4
4
6
6
9

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

0
0
0
0
0
0
0
0
11
11
11
11
13

Hint

对于第1个数据

第五天过后的传送带如下所示。

RL?

U??

?DL

一种在余下的方格上建造传送带的最优方案如下。

RLR

URR

LDL

在这种配置下，位于 (1,1)，(1,2) 和 (2,1) 的方格是不可用的。

对于第2个数据

第八天过后的传送带如下所示。 RLD

D?U

URL

无论 Farmer John 在中间建造何种传送带，所有方格都将是不可用的。

数据范围

测试点 4-5：N≤10

测试点 6-7：N≤40

测试点 8-13：没有额外限制。