题目描述

远古山脉可以看作是一个由山脉元素组成的序列，每个元素有一个高度，远

古山脉的变化规则如下：

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 \frac{m}{2} \right \rceil$个元素，那么山脉收集的能量为:

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

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

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

输入格式

文件的第一行有1个正整数$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$个山脉。

保证以上所有输入整数在long long范围内

输出格式

对于每个询问，输出一行答案，答案对1000000007取模。

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