Supercomputer - MarisaOJ: Marisa Online Judge

Supercomputer

Time limit: 1000 ms
Memory limit: 512 MB
Given an empty sequence $S$, perform a series of $t$ operations, each belonging to one of the following types: - Add an element $x$ to the end of sequence $S$. - Calculate the sum of elements having values within the range $[a,b]$. - Rearrange sequence $S$ in non-decreasing order, then calculate the sum of elements with indices from $p$ to $q$ (where $1 \le p \le q \le |S|$, and $|S|$ is the number of elements in sequence $S$). After that, append two elements to the end of sequence $S$: one with the value of the element at index $p$ plus $1$, and the other with the value of the element at index $q$ minus $1$. ### Input - The first line consists of a positive integer $t$. - The $i$-th line among the $t$ following lines describes the $i$-th operation, which is one of three types in the format: Start type $k$ ($k$ is either $1$ or $2$ or $3$). If it's operation type $1$, then it is followed by an integer $x$ ($−10^9 ≤ x ≤ 10^9$). If it's operation type $2$, then it is followed by two integers $a, b$ ($−10^9 ≤ a \le b ≤ 10^9$). If it's operation type $3$, then it is followed by two positive integers $p, q$. ### Output - Print the answers for each operation of types $2$ and $3$. ### Constraints - 40% of the tests have $t \le 1000$. - 40% of the tests have $t \le 10^5$, with no operation of type $3$. - 20% of the tests have $t \le 10^5$. ### Example Input: ``` 7 1 5 1 3 1 1 2 2 4 1 2 3 2 3 2 2 4 ``` Output: ``` 3 5 10 ```