作为一位开明的君主，Byteasar 想要在 Byteotia 王国推广移动通信。所有的城镇和村庄都坐落于一条直线上，我们将这条直线视为数轴。

新任命的皇家电信顾问需要一个程序来测试配备了收发器的基站的位置。一个收发器由一对数字 $s$ 和 $a$ 来表征，其含义如下：位于 $x$ 点的基站，其信号强度为 $s$。信号强度随着距离基站的增加而线性衰减，在距离基站 $d$ 的位置（即 $x \pm d$ 处），信号强度为 $\max(0, s - a \cdot d)$。

我们（乐观地）假设某一点的有效信号强度是所有基站信号强度的总和。

该程序应支持建立和移除基站的操作，以及查询给定区间内所有整数点上的平均有效信号强度。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$ ($n \ge 2, m \ge 1$)，由单个空格分隔，分别指定了道路的长度和要执行的操作次数。

接下来有 $m$ 行，指定了这些操作。每一行以一个字符开头，表示操作类型，后跟一到三个整数：

• “P $x$ $s$ $a$” 表示在 $x$ 点建立一个由 $s, a$ 表征的基站 ($1 \le x \le n, 1 \le s, a \le 100\,000$)。
• “U $x$” 表示从 $x$ 点移除一个基站 ($1 \le x \le n$)。
• “Z $x_1$ $x_2$” 表示查询满足 $x_1 \le x \le x_2$ 的所有整数点 $x$ 上的平均有效信号强度 ($1 \le x_1 \le x_2 \le n$)。

每一行中的符号和数字由单个空格分隔。你可以假设在执行建立操作 (P) 时，$x$ 点处没有基站；在执行移除操作 (U) 时，$x$ 点处一定有一个基站。

输出格式

输出应包含与输入中查询 (Z) 次数相同的行数；每一行应包含一个整数：对应查询结果向下取整后的值。

样例

样例输入 1

11 7
P 5 30 10
Z 6 7
P 10 22 5
Z 6 7
Z 6 6
U 5
Z 6 6

样例输出 1

15
19
22
2

说明

下表提供了样例的详细解释：

子任务

测试集由以下子任务组成。每个子任务内可能包含多个测试点。