Problem 1: Single Rotation (splay)

Country H is a nation that loves writing code, where people learn to implement various data structures from a very young age. A splay tree is a data structure that is popular because it is easy to code, versatile, and efficient; mastering it has become a mandatory skill in Country H. One day, the evil "Ka" arrived with his evil "constants," attempting to destroy Country H. "Ka" brainwashed the people of Country H, claiming that if a splay tree is implemented using single rotations, it will be faster. "Ka" called this "single-rotation splay" a "spaly." Although his claim was nonsensical, some people in Country H believed him, and little H was one of them; "spaly" immediately became his faith. The King of Country H, naturally, would not allow such a trend to spread. The King constructed a set of data consisting of $m$ (up to $10^5$) operations. He knew that such data would surely crush "spaly," but the King had many other things to do, so he entrusted the task of calculating the actual cost of each operation to you. The operations in the data are divided into 5 types:

1. Insertion: Insert a new isolated node with key $key$ into the current non-empty spaly. The insertion method is as follows: first, compare $key$ with the root. If $key$ is smaller than the root, move to the left subtree; otherwise, move to the right subtree. Repeat this until, at some point, $key$ is smaller than the current subtree root $x$ and $x$ has no left child, then make $key$ the left child of $x$; or $key$ is larger than the current subtree root $x$ and $x$ has no right child, then make $key$ the right child of $x$. The cost of this operation is: the depth of $key$ after insertion. Specifically, if the tree is empty, simply make the new node a single-node tree. (All node keys are distinct. See the description of "spaly" at the end for the definition of "depth.")
2. Single Rotate Minimum: Splay the element $xmin$ with the minimum key in the spaly to the root. The cost of this operation is: the depth of $xmin$ before the rotation. (See the description of "spaly" at the end for the explanation of the single rotation operation.)
3. Single Rotate Maximum: Splay the element $xmax$ with the maximum key in the spaly to the root. The cost of this operation is: the depth of $xmax$ before the rotation.
4. Single Rotate Delete Minimum: First perform operation 2, then delete the root. Since after operation 2 the root has no left subtree, simply sever the connection between the root and the right subtree. (See the example explanation for details.) The cost of this operation is the same as operation 2.
5. Single Rotate Delete Maximum: First perform operation 3, then delete the root. The cost of this operation is the same as operation 3.

For those who are not from Country H, you may need to understand some knowledge about "spaly" to complete the King's task:

a. A "spaly" is a binary tree that satisfies the following: for any node $x$, if it has a left child $lx$, then the key of $lx$ is less than the key of $x$. If it has a right child $rx$, then the key of $rx$ is greater than the key of $x$. b. The depth of a node in a "spaly" is defined as: the total number of nodes on the path from the root to that node (including itself). c. The single rotation operation is defined for 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 the zig(x) operation (as shown in the figure above, the tree on the left becomes the tree on the right after zig(x)), otherwise perform the zag(x) operation (in the figure above, the tree on the right becomes the tree on the left after zag(f)). Each time a zig(x) or zag(x) is performed, the depth of $x$ decreases by 1. Repeat this until $x$ becomes the root. In short, splaying $x$ means making $x$ the root by repeatedly performing zig and zag.

Input

The first line contains a single positive integer $m$ ($1 \le m \le 10^5$). The next $m$ lines each describe an operation: first is an operation number $c$ ($1 \le c \le 5$), which is the number of the operation given in the problem description. If $c = 1$, an additional non-negative integer $key$ is provided, representing the key of the newly inserted node.

Output

Output $m$ lines, each containing an integer representing the cost of the corresponding 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 key \le 10^9$. All 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.