Interactive Creative Players Collective (ICPC) 正在开发一款新的电脑游戏，他们希望在游戏中生成逼真的地貌。ICPC 的一位工程师提出了一种受地质过程启发的算法。该算法从平坦的地貌开始，通过抬升或降低连续的区块来反复修改地貌，从而形成地垒（抬升的区块）和地堑（降低的区块）。需要抬升或降低的区块是随机选择的。ICPC 希望通过这种方式获得逼真的地貌。

你的任务是解析任何此类修改序列，并输出最终的地貌。地貌由 $n$ 个整数高度值序列表示，对应 $x$ 轴上从 $1$ 到 $n$ 的每个整数点。图 E.1 展示了一个通过连接高度值并用线段表示的示例。

图 E.1：样例输入 1 生成的地貌示意图。

最初，所有 $n$ 个点的高度均为 $0$。这个平坦的形状会经历一系列修改。每次修改都会应用以下四种操作之一，并带有两个整数参数 $x_1 \le x_2$：

• R: Raise（抬升）—— 将 $x_1$ 到 $x_2$（含）之间所有点的高度增加 $1$。
• D: Depress（降低）—— 将 $x_1$ 到 $x_2$（含）之间所有点的高度减少 $1$。
• H: Hill（山丘）—— 在 $x_1$ 和 $x_2$ 之间添加一个新的线性形状的山丘。
• V: Valley（山谷）—— 在 $x_1$ 和 $x_2$ 之间添加一个新的线性形状的山谷。

向当前地貌添加山丘的方法如下：点 $x_1$ 和 $x_2$ 的高度增加 $1$。如果 $x_2 - x_1 > 1$，则点 $x_1 + 1$ 和 $x_2 - 1$ 的高度增加 $2$。如果 $x_2 - x_1 > 3$，则点 $x_1 + 2$ 和 $x_2 - 2$ 的高度增加 $3$，依此类推。图 E.2 展示了一个示例。添加山谷的方法相同，只是高度改为减少。高度的最大变化发生在 $x_1$ 和 $x_2$ 的中间。如果 $x_2 - x_1$ 为奇数，则会有两个相邻的点达到最大变化，否则只有一个点。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$，其中 $n$ ($1 \le n \le 200\,000$) 是点的数量，$k$ ($0 \le k \le 200\,000$) 是修改次数。沿 $x$ 轴的 $n$ 个点编号为 $1$ 到 $n$。接下来的 $k$ 行描述了修改操作。每行包含一个字符 $c$ 和两个整数 $x_1$ 和 $x_2$，其中 $c$（R、D、H 或 V 之一）指定操作类型，$x_1$ 和 $x_2$ ($1 \le x_1 \le x_2 \le n$) 指定其参数。

输出格式

输出 $n$ 行，其中第 $i$ 行包含按给定顺序应用所有修改后点 $i$ 的高度。

图 E.2：样例输入 2 生成的地貌示意图。

样例

样例输入 1

20 13
H 12 13
D 5 18
R 13 14
R 8 16
H 2 3
V 10 19
V 3 13
R 8 13
V 3 10
D 5 18
V 11 12
R 1 6
R 14 19

样例输出 1

1
2
0
-3
-7
-9
-11
-9
-7
-6
-6
-5
-3
-4
-5
-4
-4
-3
0
0

样例输入 2

7 1
H 1 6

样例输出 2

1
2
3
3
2
1
0