题目背景

whjkfls 的超常班里，有一条长长的走廊，从 $0$ 号教室延伸到 $N-1$ 号教室。

走廊上有一支由超常班学生组成的巡逻队。他们遵循着一条buchengwen的班规：

若前方有路，便踏前一步；若前方无路，便转身回望。

题目描述

走廊是一条长度为 $N$ 的线段，教室编号依次为 $0, 1, 2, \dots, N-1$。

巡逻队的成员（以下称为"超常班学员"）按照如下规则在走廊上移动：

• 一个在时间 $t$ 位于 $x$ 号教室、面朝西（朝编号减小的方向）的超常班学员，会在时间 $t+1$ 移动到 $x-1$ 号教室，方向不变。特别的，若 $x = 0$（已到最西端），则该学员原地转向，改为面朝东。
• 一个在时间 $t$ 位于 $x$ 号教室、面朝东（朝编号增大的方向）的超常班学员，会在时间 $t+1$ 移动到 $x+1$ 号教室，方向不变。特别的，若 $x = N-1$（已到最东端），则该学员原地转向，改为面朝西。

简言之：能走则走，不能走则原地掉头。

最初，走廊上空无一人。

现在，你作为 Haisan.club 的值周生，需要按顺序处理以下三类指令：

• W t y z —— 在时间 $t$，从 $y$ 号教室向西放出 $z$ 名超常班学员（全部面朝西）
• E t y z —— 在时间 $t$，从 $y$ 号教室向东放出 $z$ 名超常班学员（全部面朝东）
• Q t y z —— 输出时间 $t$ 时，编号在 $[y, z)$ 范围内的教室里共有多少名超常班学员

输入格式

第一行两个整数 $N, Q$，表示走廊跨越 $N$ 间教室，共有 $Q$ 条指令。

接下来 $Q$ 行，每行一条指令，格式为 $op_i\ t_i\ y_i\ z_i$，其中 $op_i$ 为 W、E、Q 之一，其余参数含义如上所述。

输出格式

对于每条 $op = Q$ 的指令，输出一行一个整数，表示该时刻指定区间内的超常班学员总数。

样例

样例 1

10 3
E 1 2 1
W 2 5 1
Q 3 4 5

2

解释：时间 $1$ 在 $2$ 号教室放 $1$ 人向东，时间 $2$ 他走到 $3$ 号教室；时间 $2$ 在 $5$ 号教室放 $1$ 人向西，时间 $3$ 他走到 $4$ 号教室。查询 $[4, 5)$ 即 $4$ 号教室，有 $2$ 人。

样例 2

5 4
W 1 1 2
E 2 4 2
Q 3 2 4
Q 5 2 4

0
4

解释：时间 $1$ 在 $1$ 号教室放 $2$ 人向西，他们走到 $0$ 号教室后于时间 $2$ 原地转向向东；时间 $2$ 在 $4$ 号教室放 $2$ 人向东，他们于时间 $3$ 走到 $0$ 号教室（$4 o 5$ 转向，$5 o 4 o 3 o 2 o 1 o 0$）。查询 $[2, 4)$ 在时间 $3$ 时为空；时间 $5$ 时，$4$ 名学员均在 $[2, 4)$ 区间内。

样例 3

10 10
Q 1 3 8
W 2 1 2
E 3 7 3
Q 4 1 5
Q 5 0 6
W 6 2 3
E 7 3 5
Q 8 2 10
E 9 7 1
W 10 6 1

0
0
2
10

数据范围

• 对于 $20\%$ 的数据：$N \le 100$，$Q \le 100$，当 $op = W$ 或 $op = E$ 时，$1 \le z_i \le 100$。
• 对于 $100\%$ 的数据：
  • $1 \le N \le 2 imes 10^5$
  • $1 \le Q \le 8 imes 10^4$
  • $0 \le t_1 < t_2 < \dots < t_Q \le 10^8$
  • 当 $op = W$ 或 $op = E$ 时：$0 \le y_i < N$，$1 \le z_i \le 10^8$
  • 当 $op = Q$ 时：$0 \le y_i < z_i \le N$