In computer science, a treap is a binary search tree according to the keys and meanwhile a heap according to the weights.

Your task is to maintain a max-treap supporting the following operations:

• 0 k w: Insert a new node, whose key and weight are k and w.
• 1 k: Delete a node in the treap with key k.
• 2 ku kv: Return the distance between node u whose key is ku and node v whose key is kv.

No two nodes share a same key or same weight, and we guarantee the node is indeed in the treap before a delete operation takes place.

Input

The first line contains an integer N (1 ≤ N ≤ 200000), the number of operations. The next N lines each contains two or three integers "0 k w", "1 k" or "2 ku kv" (0 < k, w, ku, kv ≤ maxlongint).

Output

For each query operation, print the distance between u and v.

Example

Input:
12
0 4 17535
0 10 38964
0 2 21626
0 1 61321
2 1 10
2 10 4
1 10
1 1
0 8 42634
2 8 4
2 8 2
2 4 2
Output:
1
2
2
1
1