134. Reconstruct A Binary Tree

Task Description

Write a program to reconstruct a binary search tree and find the distances of some key pairs. You will be given the keys and their level number in the binary search tree. The level of a tree node is recursively defined as follows.

• The level of the root is 1
• If a node is not the root, then its level is the level of its parent plus 1.

We will ask you to compute the distance of each key pair in the following input. Now given the keys, their level numbers, and key pairs to evaluate, you must reconstruct the binary search tree, and output the distance for each key pair.

p134

Input

The first line of the input is the number of tree nodes ($N$). Each of the next $N$ lines has the key, then the level number of the key. Then there is a number $P$, with $P$ pairs of keys in the following. You may assume that all keys are different. Also the two keys in every key pair are different. Keys and level numbers are all integers between $-2^{31}$ and $2^{31}-1$. $N \le 1000$

Output

The output has $P$ lines. The $i$-th line is the distance of The output has $N$ lines. The $i$-th line has the $i$-th key in pre-order tree traversal.

Sample Input

76 13 24 41 32 47 25 333 65 72 4


Sample Output

134


Testdata Set

Download Testdata