Problem Description

You are undergoing an interview at DISCO Corporation. Before the interview, you were given a binary search tree $ T $ consisting of $ 0 $ nodes.

You were given the following $ Q $ queries by the interviewer to process in the given order. You decided to process the $ Q $ queries quickly to impress the interviewer.

Here are the types of queries:

1. 1 v : Insert a node with value $ v $ at the appropriate position in $ T $.
2. 2 v : For a node $ u $ in $ T $ with value $ v $, output the height difference $h(lst)\ -\ h(rst)$ between the left subtree $ lst $ and the right subtree $ rst $.
3. 3 v : If the node $ u $ in $ T $ with value $ v $ has a left child, perform a right rotation on $ u $. If it does not have a left child, output -1.
4. 4 v : If the node $ u $ in $ T $ with value $ v $ has a right child, perform a left rotation on $ u $. If it does not have a right child, output -1.

In the type 1 queries, it is guaranteed that a node with value $ v $ does not exist in $ T $. In the type 2, 3, and 4 queries, it is guaranteed that a node with value $ v $ exists in $ T $.

• The height of a binary search tree $ T $ is defined as follows:

• The height $ h(u) $ of a binary search tree rooted at node $ u $ is $h(u)\ =\ max(h(lst),\ h(rst))+1$, where $ lst $ is the left subtree and $ rst $ is the right subtree of $ u $.

• If $ u $ does not have a left subtree $ lst $, treat $h(lst)\ =\ 0$.
• Similarly, if $ u $ does not have a right subtree $ rst $, treat $h(rst)\ =\ 0$.
• The operation of inserting a node $ u $ into the binary search tree $ T $ is performed as follows. Note that the result of this operation is uniquely determined given $ T $ and $ u $.

1. If $ T $ consists of $ 0 $ nodes, make $ T $ a binary search tree rooted at $ u $ and end the process.

2. If $ T $ consists of one or more nodes, insert $ u $ as a child of some node such that the following conditions are satisfied:

   • A node $ w $ can have at most $ 2 $ direct children (referred to as the left child and the right child).
   • The value of any node that is a left descendant of $ w $ is less than the value of $ w $.
   • The value of any node that is a right descendant of $ w $ is greater than or equal to the value of $ w $.
   • The right rotation of a node $ u $ in the binary search tree $ T $ is performed as follows. This operation cannot be performed if $ u $ does not have a left child.

3. Let the left child of $ u $ be $ l $.

4. Remove the edge connecting $ u $ and $ l $. If $ u $ has a parent $ p $, remove the edge connecting $ u $ and $ p $ and connect $ p $ as the parent of $ l $.
5. If $ l $ has a right child $ r $, remove the edge connecting $ l $ and $ r $ and connect $ r $ as the left child of $ u $.

6. Connect $ u $ as the right child of $ l $.
   - The left rotation of a node $ u $ in the binary search tree $ T $ is performed as follows. This operation cannot be performed if $ u $ does not have a right child.

7. Let the right child of $ u $ be $ r $.

8. Remove the edge connecting $ u $ and $ r $. If $ u $ has a parent $ p $, remove the edge connecting $ u $ and $ p $ and connect $ p $ as the parent of $ r $.
9. If $ r $ has a left child $ l $, remove the edge connecting $ r $ and $ l $ and connect $ l $ as the right child of $ u $.
10. Connect $ u $ as the left child of $ r $.

Input Format

The input is given from the standard input in the following format:

$ Q $ $ t_1 $ $ v_1 $ $ . $ $ . $ $ . $ $ t_Q $ $ v_Q $

• The first line contains an integer $Q\ (1≦Q≦400,000)$ representing the number of queries.
• The following $ Q $ lines each contain two integers $t_i,\ v_i(1≦t_i≦4,1≦v_i≦400,000)$ separated by a space, representing the type of the $ i $ -th query and the value of the node.
• In type 1 queries, it is guaranteed that a node with value $ v $ does not exist in $ T $.
• In type 2, 3, and 4 queries, it is guaranteed that a node with value $ v $ exists in $ T $.

Output Format

Output the result of each query in the given order, one per line. Note that the output should be one of the following three types:

1. Type 2 queries
2. Type 3 queries where the node with value $ v $ does not have a left child
3. Type 4 queries where the node with value $ v $ does not have a right child

Sample Input and Output

Sample Input #1

13
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
2 1
2 2
2 4
2 6
2 7

Sample Output #1

0
0
-1
-1
-1

Sample Input #2

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
3 4
2 2
2 4
2 6
2 7
3 7

Sample Output #2

-3
-2
-1
-1
-1

Sample Input #3

14
1 4
1 2
1 1
1 3
1 6
1 5
1 7
1 8
4 6
2 2
2 4
2 6
2 7
4 6

Sample Output #3

0
-1
1
1
-1

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $ 1≦Q≦1,000 $, you will get $ 20 $ points.
• If you solve the dataset where $ 1≦t_i≦2(1≦i≦Q) $, you will get an additional $ 30 $ points.
• If you solve the dataset without additional constraints, you will get an additional $ 100 $ points, totaling $ 150 $ points.

Sample Explanation 1

• From the 1st to the 8th query, nodes are inserted into $ T $ in the order given by the queries. Note that no rotation operation is performed during insertion.
• The figure below shows $ T $ after the 8th query.
• The value written inside the node represents the value of the node, and the value written next to the node represents the height of the subtree rooted at that node.
• The shape of $ T $ is uniquely determined by the given queries.
• In the 9th query, since both the height of the left subtree $ h(lst) $ and the right subtree $ h(rst) $ of the node with value $ 1 $ are $ 0 $, $ h(lst)-h(rst) $ is $ 0 $.
• In the 10th query, since both $ h(lst) $ and $ h(rst) $ are $ 1 $, $ h(lst)-h(rst) $ is $ 0 $.
• In the 11th query, since $ h(lst) $ is $ 2 $ and $ h(rst) $ is $ 3 $, $ h(lst)-h(rst) $ is $ -1 $.
• In the 12th query, since $ h(lst) $ is $ 1 $ and $ h(rst) $ is $ 2 $, $ h(lst)-h(rst) $ is $ -1 $.
• In the 13th query, since $ h(lst) $ is $ 0 $ and $ h(rst) $ is $ 1 $, $ h(lst)-h(rst) $ is $ -1 $.
• Note that the height of a subtree with no children is $ 0 $.
• This case satisfies both partial point constraints.

Sample Explanation 2

• The figure below shows $ T $ before (left) and after (right) the right rotation performed by the 9th query.
• Pay attention to the change in the positional relationship between nodes.
• In the 14th query, since the node with value $ 7 $ does not have a left child, output -1.
• The shape of $ T $ is uniquely determined by the given queries.
• This case satisfies the first partial point constraint.

Sample Explanation 3

• The figure below shows $ T $ before (left) and after (right) the left rotation performed by the 9th query.
• Pay attention to the change in the positional relationship between nodes.
• In the 14th query, since the node with value $ 6 $ does not have a right child, output -1.
• The shape of $ T $ is uniquely determined by the given queries.
• This case satisfies the first partial point constraint.

见题面 Input 部分

见题面 Output 部分