题目描述

交互性创意玩家群（Interactive Creative Players Collective, ICPC）正在开发一款新游戏，在这款游戏中，他们希望生成真实地形。ICPC 中的一个工程师受地质运动的启发，提出了一个算法。这个算法从一块平地开始，通过抬升或降低一段连续的地面来反复修改，这样就形成了地垒（被抬升的地面）和地堑（被降低的地面）。这些升降的地面都是随机选取的。ICPC 希望借此能够获得真实地形。

你的任务是解释这样的修改，并最终输出得到的地形。地形用一个长度为 $n$ 的整数数列表示，每个整数代表 $x$ 轴上 $1$ 到 $n$ 的整数点的高度。图 E.1. 中展示了将高度值用线段连接起来的一个例子。

初始时，所有 $n$ 个点处高度均为 $0$。之后的一系列的修改都在此进行。每次修改都会进行如下四种操作中的一种，同时附加两个整数参数 $x_1\le x_2$：

• $\texttt R$：抬升操作，将从 $x_1$ 到 $x_2$ 的所有点都抬升 $1$ 高度（包括两端）。
• $\texttt D$：降低操作，将从 $x_1$ 到 $x_2$ 的所有点都降低 $1$ 高度（包括两端）。
• $\texttt H$：造山，在 $x_1$ 到 $x_2$ 之间添加一座线性形状的山。
• $\texttt V$：造谷，在 $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)$ 表示修改的次数。这 $n$ 个点沿 $x$ 轴排列，依次编号为 $1$ 到 $n$。

接下来 $k$ 行描述修改。每行包含一个字符 $c$ 和两个整数 $x_1,x_2$。其中 $c$（$\texttt R$, $\texttt D$, $\texttt H$ 和 $\texttt V$ 中的一个）表示操作类型，$x_1$ 和 $x_2\ (1\le x_1\le x_2\le n)$ 指定了操作的参数。

输出格式

输出 $n$ 行，第 $i$ 行表示按顺序进行所有修改后点 $i$ 的高度。

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
2
0
-3
-7
-9
-11
-9
-7
-6
-6
-5
-3
-4
-5
-4
-4
-3
0
0

7 1
H 1 6

1
2
3
3
2
1
0