Description

An ancient mountain range can be regarded as a sequence of mountain elements, each with a height. The evolution rules are as follows:

1. I h x: Insert a mountain element of height $h$ to the right of the $x$-th mountain element.
2. R l r: Reverse the heights of the mountain elements from the $l$-th to the $r$-th. For example, $a_1,a_2,a_3,a_4,a_5$, reversing $(2,5)$ becomes $a_1,a_5,a_4,a_3,a_2$.
3. M t x: Insert the $t$-th mountain to the right of the $x$-th mountain element.

Mountain elements are numbered from $1$ from left to right. Initially there are no mountain elements, denoted as the $0$-th mountain. For the $i$-th mountain, after applying any one operation it becomes the $(i+1)$-th mountain. The mountain collects energy as follows: suppose the index of the highest mountain element is $x$. If there are $m$ elements with the same maximum height, take the $\left \lceil \frac{m}{2} \right \rceil$-th one from the left. Then the collected energy is:

$$\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.$$

Here $h_{i}$ denotes the height of the $i$-th mountain element.

The basic query to answer is: for the sub-mountain formed by the mountain elements from the $l$-th to the $r$-th, how much energy can be collected?

Input Format

The first line contains a positive integer $n$ ($n\le 50000$), the total number of operations and queries.

Then follow $n$ lines, each in one of the following four formats:

1. I h x: Insert a mountain element of height $h$ to the right of the $x$-th mountain element, $0\le h\le 20000$.
2. R l r: Reverse the heights from the $l$-th mountain element to the $r$-th mountain element.
3. M t x: Insert the $t$-th mountain to the right of the $x$-th mountain element.
4. Q l r: Query the energy collected by the sub-mountain formed by the $l$-th to the $r$-th mountain elements.

For the $i$-th mountain, after applying any one operation it becomes the $(i+1)$-th mountain.

All input integers fit in the range of long long.

Output Format

For each query, output the answer on one line, modulo 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

Hint

Translated by ChatGPT 5