COT5 - Count on a treap

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 < kwkukv ≤ 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

Added by:Fotile
Date:2012-12-09
Time limit:1.220s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2022-09-09 10:37:11 [Rampage] Blue.Mary
I'm not sure if this problem has a solution with complexity O(logn) per query. If desired solution has complexity O(log^2n) per query, then the time limit is very tight indeed.
2015-11-04 09:31:51 Philips
@psetter : please enable submissions.
2014-03-26 22:37:38 Francky
@psetter : please enable submissions. Problem hidden waiting for that. After that, it can be back to classical.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.