题目背景

翻译来自于 LibreOJ。

题目描述

题目译自 XXV Olimpiada Informatyczna — II etap Przekaźniki telekomunikacyjne

国王 Bajtazar 顺应时代潮流，决定为拜托尼亚王国铺设移动电话网络，覆盖所有村庄和城市。这些地点分布在一条笔直的道路上，可视为数轴。

新任命的电信顾问需要一个程序，测试中继站天线杆的位置。每根天线杆顶端装有中继站，由参数 $s$ 和 $a$ 描述。在杆位置 $x$，信号强度为 $s$；在其他点，信号强度随距离线性下降，即在点 $x \pm d$，强度为 $\max(0, s - a \cdot d)$。

道路上某点的信号覆盖强度为所有中继站信号强度的总和。

程序需支持添加或移除天线杆，以及查询某段整数点平均信号覆盖强度的操作。

输入格式

第一行包含两个整数 $n, m$ $(n \geq 2, m \geq 1)$，分别表示道路长度和操作数量。

接下来的 $m$ 行描述操作，每行以单个字符开头，表示操作类型，后跟一至三个整数：

• $\texttt{P}\ x\ s\ a$：在点 $x$ 架设天线杆，安装中继站，参数为 $s, a$ $(1 \leq x \leq n, 1 \leq s, a \leq 100000)$。
• $\texttt{U}\ x$：移除点 $x$ $(1 \leq x \leq n)$ 的天线杆。
• $\texttt{Z}\ x_1\ x_2$：查询区间 $[x_1, x_2]$ 内所有整数点 $x$ $(x_1 \leq x \leq x_2, 1 \leq x_1 \leq x_2 \leq n)$ 的平均信号覆盖强度。

各行数据以单空格分隔。保证操作 $\texttt{P}$ 时点 $x$ 无天线杆，操作 $\texttt{U}$ 时点 $x$ 有天线杆。

输出格式

输出与输入中 $\texttt{Z}$ 操作数量相同的行，每行包含一个整数，表示对应查询的平均信号覆盖强度，向下取整。

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

15
19
22
2

提示

样例 1 解释

附加样例

1. $n=101, m=500$，道路首尾中各一杆，随机查询。
2. $n=300000$，点 $1$ 有一杆，$s=100000, a=100$，查询各前缀 $[1, i]$ 的平均强度，$1 \leq i \leq 300000$。
3. $n=300000, m=500000$，每点有杆，$s=1000, a=1$，查询整条路的平均强度。

详细子任务附加限制及分值如下表所示。