问题陈述
N 蚂蚁编号 1 通过 N 在数轴上,
其正方向指向右侧。
在 初始状态,蚂蚁 i 位于初始坐标处 X_i 并面向角色描述的方向 D_i。
具体来说, D_i= R 表示面向右,并且 D_i= L 表示朝左。
在此,可以保证 X_1,X_2,\dots,和 X_N 是成对不同的偶数。
一旦 Snuke 打响指,蚂蚁就会开始按照以下规则移动。
- 每只蚂蚁的移动速度为 1 每秒在其面向的方向上。
- 每当两只蚂蚁到达同一坐标时,它们就会翻转方向并继续移动。 这个事件被称为 碰撞 发生 蚂蚁。 可以证明三只或更多蚂蚁永远不会同时到达同一坐标。
您总共获得 Q 查询,以下每种类型之一。 按顺序处理它们。
1 x d:添加具有初始坐标的蚂蚁 x 和初始方向 d 到初始状态。 在此,可以保证 x 是偶数,并且与任何蚂蚁的初始坐标都不重合。2 l r: 如果 Snuke 当时打响指 0,让 t_1,t_2,\dots 是蚂蚁的时间 1 与其他蚂蚁发生碰撞,按时间顺序列出。 评价 t_{l}+t_{l+1}+\dots +t_{r} 并打印。 可以保证 l \leq r 和蚂蚁 1 至少与其他蚂蚁发生碰撞 r 次。
请注意,第二种类型的查询是独立的。 换句话说,处理第二类型的查询实际上并不修改蚂蚁的初始状态。
约束
- N 和 Q 是整数。
- 1\leq N,Q \leq 10^5
- X_i 是偶数。
- |X_i| \leq 10^9
- X_i \neq X_j\ (i \neq j)
- D_i is
RorL. - 对于第一种查询,
- x 是偶数。
- |x| \leq 10^9
- 在处理查询时,没有具有初始坐标的蚂蚁 x.
- d is
RorL.
- 对于第二类的每个查询,
- l 和 r 是整数。
- 1 \leq l \leq r \leq M,其中 M 是 ant 的次数 1 与其他蚂蚁发生碰撞,从处理查询时的初始状态开始。
输入
输入由标准输入按以下格式给出:
N Q
X_1 D_1
X_2 D_2
\vdots
X_N D_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 表示 i-th 查询,采用以下格式之一:
1 x d
2 l r
输出
如果有 T 第二类查询,打印 T 行。 在 i-th (1\leq i \leq T) 行,打印答案 i-第一个这样的查询。
示例输入 1
2 5 2 R 10 L 2 1 1 1 0 L 1 -2 R 2 1 2 2 2 2
示例输出 1
4 10 6
如果 Snuke 在处理查询之前在初始状态下打响指,蚂蚁的移动方式如下。
- 时间 0,所有蚂蚁开始移动。 两只蚂蚁面朝左,面朝右。
- 时间 4\ (:=t_1),蚂蚁 1 和 2 在坐标处碰撞 6。 现在两只蚂蚁面朝左、面朝右。
因此,答案 1-st 查询是 t_1=4.
如果 Snuke 在处理前三个查询的初始状态下打响指,蚂蚁的移动方式如下。 这里我们将添加的蚂蚁称为 2-nd 和 3-rd 查询蚂蚁 3 和蚂蚁 4。
- 时间 0,所有的蚂蚁开始移动。 四只蚂蚁分别面向右、左、左、右。
- 时间 1,蚂蚁 3 和 4 在坐标处发生碰撞 -1。 现在,四只蚂蚁面朝右、左、右、左。
- 时间 4\ (:=t_1),蚂蚁 1 和 2 在坐标处发生碰撞 6。 现在,四只蚂蚁面朝左、右、右、左。
- 时间 6\ (:=t_2),蚂蚁 1 和 3 在坐标处发生碰撞 4。 现在,四只蚂蚁面朝右、右、左、左。
因此,答案 4-第一个查询是 t_1+t_2=10,以及答案 5-第一个查询是 t_2=6.
示例输入 2
10 10 0 R 16 L 94 L -96 R -24 L 52 R -10 L -38 L 50 R 98 L 1 -66 L 2 2 3 1 48 L 1 34 R 2 2 2 1 8 L 2 2 3 2 2 3 1 62 L 2 1 3
示例输出 2
151 56 108 108 112