题目背景

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

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

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

作为值周生，你需要快速统计任意时刻、任意区间内有多少名学员。走廊很长，学员很多，如果逐个教室清点，时间根本不够。这时候，你需要一种能快速区间求和的数据结构——树状数组（Binary Indexed Tree，简称 BIT）。

---

树状数组（BIT）简介

树状数组是一种维护序列前缀和的数据结构，支持两种操作：

操作	时间复杂度
单点修改（给某个位置加 $v$）	$O(\log N)$
前缀查询（求 $[0, x]$ 的和）

通过前缀查询的差分，可以在 $O(\log N)$ 内得到任意区间和。

---

BIT 的核心思想

BIT 利用了整数的二进制拆分。

每个正整数 $x$ 都可以唯一拆成若干个 $2$ 的幂次之和。例如：

$$13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$$

BIT 中，每个节点 $tree[x]$ 维护一个长度为 $lowbit(x)$ 的区间和，其中：

$$lowbit(x) = x \ \& \ (-x)$$

表示 $x$ 的二进制表示中最低位的 $1$ 所对应的值。

$x$	二进制	$lowbit(x)$	$tree[x]$ 维护的区间
$1$	$0001$	$1$	$[0, 0]$
$2$	$0010$	$2$	$[0, 1]$
$3$	$0011$	$1$	$[2, 2]$
$4$	$0100$	$4$	$[0, 3]$
$5$	$0101$	$1$	$[4, 4]$
$6$	$0110$	$2$	$[4, 5]$
$7$	$0111$	$1$	$[6, 6]$
$8$	$1000$	$8$	$[0, 7]$

---

单点修改

给位置 $x$ 增加 $v$ 时，需要更新所有包含 $x$ 的节点：

void add(int x, long long v) {
    for (++x; x <= N; x += x & -x)  // x += lowbit(x)，跳到父节点
        tree[x] += v;
}

例如修改位置 $5$：$x = 6 \to 8 \to 16 \to \dots$，更新 $tree[6]$（区间 $[4,5]$）、$tree[8]$（区间 $[0,7]$）等。

---

前缀查询

求 $[0, x]$ 的和时，把 $x$ 拆成若干 $lowbit$ 段累加：

long long sum(int x) {
    long long res = 0;
    for (++x; x > 0; x -= x & -x)  // x -= lowbit(x)，跳到前一个区间
        res += tree[x];
    return res;
}

例如查询前缀到 $5$：$x = 6 \to 4 \to 0$，累加 $tree[6]$（$[4,5]$）+ $tree[4]$（$[0,3]$）= $[0,5]$。

---

区间查询

区间 $[l, r]$ 的和 = 前缀到 $r$ 减去前缀到 $l-1$：

long long range(int l, int r) {
    return sum(r) - sum(l - 1);
}

题目描述

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

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

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

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

最初，走廊上空无一人。

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

• 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$ 号教室，时间 $3$ 走到 $4$ 号教室；时间 $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$ 人向西，他们于时间 $2$ 走到 $0$ 号教室，因前方无路而原地转向东；时间 $2$ 在 $4$ 号教室放 $2$ 人向东，由于 $4$ 号已是走廊最东端，他们原地转向西。时间 $3$ 时，第一批学员走到 $1$ 号教室，第二批仍在 $4$ 号教室，查询 $[2, 4)$ 为空。时间 $5$ 时，第一批学员移动至 $3$ 号教室，第二批移动至 $2$ 号教室，共 $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 \times 10^5$
  • $1 \le Q \le 8 \times 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$