题目描述

远古山脉可以看作是一个由山脉元素组成的序列，每个元素有一个高度，远古山脉的变化规则如下：

1. I h x：在第 $x$ 个山脉元素右边插入高度为 $h$ 的山脉元素。

2. R l r：从第 $l$ 个山脉元素到第 $r$ 个山脉元素的高度翻转，例如，$a_1,a_2,a_3,a_4,a_5$，对 $[2,5]$ 翻转就变为 $a_1,a_5,a_4,a_3,a_2$。

3. M t x：在第 $x$ 个山脉元素右边插入第 $t$ 个山脉。

山脉元素按从左到右的顺序从 $1$ 开始编号。一开始时没有山脉元素，记为第 $0$ 个山脉。对于第 $i$ 个山脉，经过任意一种变化后就变成第 $i+1$ 个山脉。山脉中会收集山脉能量，假设山脉中最高的山脉元素的编号为 $x$，如果有 $m$ 个相同的高度，取左数第$\left \lceil \dfrac{m}{2} \right \rceil$个元素，那么山脉收集的能量为:

$$\sum_{i=l}^{x-1}\left\{\begin{matrix} x-i & ,\ h_{i}>h_{i+1}\\ 0 & ,\ h_{i}\leq h_{i+1} \end{matrix}\right.+\sum_{i=x+1}^{r}\left\{\begin{matrix} i-x & ,\ h_{i}>h_{i-1}\\ 0 & ,\ h_{i}\leq h_{i-1} \end{matrix}\right. $$

其中 $h_i$ 代表第 $i$ 个山脉元素的高度。

山脉序列问题需要回答的基本询问是：从第 $l$ 个山脉元素到第 $r$ 个山脉元素组成子山脉能收集的能量是多少？

输入格式

文件的第一行有一个正整数 $n$（$n\le 50000$），表示山脉变化和询问的总次数。

接下来 $n$ 行，每行是四种格式之一：

1. I h x: 在第 $x$ 个山脉元素右边插入高度为 $h$ 的山脉元素，$0\le h\le 20000$。

2. R l r: 从第 $l$ 个山脉元素到第 $r$ 个山脉元素的高度翻转。

3. M t x: 在第 $x$ 个山脉元素右边插入第 $t$ 个山脉。

4. Q l r: 询问由第 $l$ 个山脉元素到第 $r$ 个山脉元素组成子山脉能收集的能量是多少。

对于第 $i$ 个山脉，经过任意一种变化后就变成第 $i+1$ 个山脉。

保证以上所有输入整数在 C++ 的 long long 范围内。

输出格式

对于每个询问，输出一行答案，答案对 $10^9+7$ 取模。

10
I 1 0
I 2 1
I 3 1
Q 1 3
I 4 3
Q 1 4
R 2 4
Q 1 4
M 3 4
Q 2 7

0
2
2
6