E. Tao of Trees (more treaps)
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Did you solve the previous problem? You surely realized that treaps don't seem more useful than a regular std::set. This is going to change now.

Since we have implemented the treaps ourselves, we can easily extend them to do more things. The situation is very similar to segment trees: they are not just useful to store individual elements, but they can also store additional information that allows us to do bulk queries or updates faster.

We will ask you to implement the easiest of those extensions for treaps: compute the order of an element, and find the element with a given order. The order of an element of key $$$k$$$ is its (0-based) index when you traverse the treap in preorder (that is, from smaller to largest key, or from left to right). If you are familiar with GNU C++ STL PBDS containers, you might know these operations as order_of_key and find_by_order.

How can we implement this in logarithmic time? Make every node have its size precomputed, where the size of a node is just the number of nodes of the subtreap rooted at it. To find the element of order $$$t$$$ in a treap, compare $$$t$$$ with the size of the root's left child: if the size is larger than $$$t$$$, the element must be in the left child; if the size is exactly $$$t$$$, the element is the root; if the size is less than $$$t$$$, the element is in the right child.

The only difficulty is to make sure that, whenever split and join operations modify the treaps, these precomputed sizes don't get outdated. To show us that you can handle that, we will ask you to write a program that implements the following operations efficiently.

  • ADD $$$k$$$ $$$h$$$: Add a node $$$K$$$ with key $$$k$$$ and height $$$h$$$ into the treap. Use 1 split and 2 joins.
  • DEL $$$k$$$: Delete the node with key $$$k$$$ from the treap $$$T$$$, using 2 splits and 1 join.
  • ORDER_OF_KEY $$$k$$$: Find the order of the key $$$k$$$, or $$$-1$$$ if it does not exist.
  • FIND_BY_ORDER $$$i$$$: Find the key of order $$$i\geq 0$$$, or $$$-1$$$ if the treap has $$$i$$$ elements or fewer.
Input

Starting with an empty treap, execute a sequence of orders, as described. Integers $$$k$$$ will be from $$$0$$$ to $$$10^5$$$, heights $$$h$$$ will be from $$$0$$$ to $$$10^9$$$. All requested indexes and orders will be non-negative numbers.

At all times the nodes in the tree will not have repeated keys or heights. We will not ask you to remove nodes that do not exist.

Output

For each command ORDER_OF_KEY or FIND_BY_ORDER, output a line with the corresponding answer.

Examples
Input
ADD 1 23
ADD 2 19
ADD 4 95
ADD 6 13
ADD 8 25
ADD 9 71
ORDER_OF_KEY 1
ORDER_OF_KEY 2
ORDER_OF_KEY 4
ORDER_OF_KEY 6
ORDER_OF_KEY 8
ORDER_OF_KEY 9
ORDER_OF_KEY 10
FIND_BY_ORDER 0
FIND_BY_ORDER 1
FIND_BY_ORDER 2
FIND_BY_ORDER 3
FIND_BY_ORDER 4
FIND_BY_ORDER 5
FIND_BY_ORDER 6
Output
0
1
2
3
4
5
-1
1
2
4
6
8
9
-1
Input
ADD 0 50
ADD 1 74
ADD 2 23
DEL 1
ADD 3 91
ADD 4 43
ADD 5 17
DEL 3
ADD 9 65
ADD 8 35
ADD 1 74
ADD 7 92
DEL 9
ADD 6 36
ADD 3 19
ADD 9 66
ORDER_OF_KEY 3
ORDER_OF_KEY 5
ORDER_OF_KEY 9
ORDER_OF_KEY 0
FIND_BY_ORDER 4
FIND_BY_ORDER 7
FIND_BY_ORDER 2
FIND_BY_ORDER 1
Output
3
5
9
0
4
7
2
1