b. The depth of a node in a splay tree is defined as: the total number of nodes on the path from the root to that node (inclusive).
c. A splay operation is performed on a node $x$ in a tree. Initially, let $f$ be the parent of $x$ in the tree. If $x$ is the left child of $f$, perform a zig(x) operation (as shown in the figure above, the tree on the left is transformed into the tree on the right via zig(x)), otherwise perform a zag(x) operation (as shown in the figure above, the tree on the right is transformed into the tree on the left via zag(f)). Each time a zig(x) or zag(x) operation is performed, the depth of $x$ decreases by 1. This is repeated until $x$ becomes the root. In short, a splay operation makes $x$ the root by repeatedly performing zig and zag operations.
Input
The input file is named splay.in.
The first line contains a single positive integer $m$ ($1 \le m \le 10^5$).
The following $m$ lines each describe an operation: first, an operation code $c$ ($1 \le c \le 5$), corresponding to the 5 types of operations described in the problem. If $c=1$, an additional non-negative integer key is provided, representing the key of the inserted node.
Output
The output file is named splay.out.
Output $m$ lines, each containing one integer, where the $i$-th line corresponds to the cost of the $i$-th input operation.
Examples
Input 1
5 1 2 1 1 1 3 4 5
Output 1
1 2 2 2 2
Constraints
20% of the data satisfies: $1 \le m \le 1000$. An additional 30% of the data satisfies: operations 4 and 5 do not exist. 100% of the data satisfies: $1 \le m \le 10^5$; $1 \le \text{key} \le 10^9$. All inserted keys are distinct. Any non-insertion operation is guaranteed to be performed on a non-empty tree. The tree is empty before any operations are performed.
Problem 2: Soul Eater (sf)
Description
Soul Eater, Saimon, is said to possess the soul of a poet. In fact, he has devoured thousands of poets' souls. Over the centuries, he has collected various kinds of souls, including poets, shepherds, emperors, beggars, slaves, sinners, and, of course, heroes.
Every soul has its own combat power, and the Soul Eater uses these combat powers to enhance his own attacks.
Saimon has $n$ souls, which can be arranged in his vast body, labeled 1 to $n$ from left to right. The combat power of the $i$-th soul is $k[i]$. Souls provide combat power to the Soul Eater in pairs. For a pair of souls $i, j$ ($i < j$): If there is no $k[s]$ ($i < s < j$) greater than $k[i]$ or $k[j]$, they provide $p1$ combat power to the Soul Eater (this can be understood as: if $j=i+1$, there is no $s$ such that $i < s < j$, so $k[s]$ does not exist, thus providing $p1$ combat power; if $j > i+1$, and $\max\{k[s] \mid i < s < j\} \le \min\{k[i], k[j]\}$, they provide $p1$ combat power). In another case, let $c$ be the maximum value among $k[i+1], k[i+2], \dots, k[j-1]$. If $c$ satisfies $k[i] < c < k[j]$ or $k[j] < c < k[i]$, they provide $p2$ combat power to the Soul Eater. If such a $c$ does not exist, they naturally do not provide $p2$ combat power. For other pairs, no combat power is provided to the Soul Eater.
The Soul Eater's friend, the Soul-Devouring Ghost, was captivated by these souls when he visited the Soul Eater's body one day. He wants to know, for any given interval $[a, b]$ ($1 \le a < b \le n$), how much combat power the souls located within this interval provide to the Soul Eater, i.e., consider the sum of combat power provided by all soul pairs $i, j$ satisfying $a \le i < j \le b$.
It is worth mentioning that the combat powers of the souls form a permutation of 1 to $n$: $k[1], k[2], \dots, k[n]$.
Input
The input file is named sf.in.
The first line contains $n, m, p1, p2$.
The second line contains $n$ integers: $k[1], k[2], \dots, k[n]$.
The following $m$ lines each contain two integers $a, b$, representing a query for the combat power provided by soul pairs in the interval $[a, b]$.
Output
The output file is named sf.out.
Output $m$ lines, each containing one answer, corresponding to the $m$ queries in order.
Examples
Input 1
10 5 2 3 7 9 5 1 3 10 6 8 2 4 1 7 1 9 1 3 5 9 1 5
Output 1
30 39 4 13 16
Constraints
30% of the data satisfies: $1 \le n, m \le 500$. An additional 30% of the data satisfies: $p1 = 2 \times p2$. 100% of the data satisfies: $1 \le n, m \le 200000$; $1 \le p1, p2 \le 1000$.