Blood Brothers Strike Back#4625

Blood Brothers Strike Back

1 second

256 megabytes

Very hard

Polycarp has come across a family tree that outlines the relationships among $n$ individuals, numbered from $1$ to $n$ . Each person in this tree can have at most one direct ancestor. Additionally, each person owns a horse of a specific type, where person $x$ has a horse of type $t_{x}$ t_x. Note that horse types may not be unique.

A person numbered $a$ is called a $1$ -ancestor of a person numbered $b$ if $a$ is a direct ancestor of $b$ .

For $k > 1$ k > 1, a person numbered $a$ is a $k$ -ancestor of a person numbered $b$ if $b$ has a $1$ -ancestor, and $a$ is a $(k - 1)$ (k-1)-ancestor of that $1$ -ancestor of $b$ .

The family tree is acyclic, meaning no person is their own ancestor, either directly or indirectly (i.e., no person is an $x$ -ancestor of themselves for any $x > 0$ x > 0).

A person numbered $a$ is a $k$ -son of a person numbered $b$ if $b$ is a $k$ -ancestor of $a$ .

Polycarp is curious about the number and types of horses owned by people. He has noted down $m$ pairs of numbers $v_{i}$ v_i, $k_{i}$ k_i. Your task is to determine the horse value of the set of $k_{i}$ k_i-sons of the person numbered $v_{i}$ v_i for each pair $v_{i}$ v_i, $k_{i}$ k_i.

The horse value of a set of people $p_{1}, p_{2}, \dots, p_{r}$ p_1, p_2, \ldots, p_r ( $p_{1} < p_{2} < \dots < p_{r}$ p_1 < p_2 < \ldots < p_r) is calculated as $(t_{p_{1}} \to (t_{p_{2}} \to (\dots \to t_{p_{r}})))$ (t_{p_1} \rightarrow (t_{p_2} \rightarrow (\ldots \rightarrow t_{p_r}))). If the set is empty, the horse value is zero. The operation $x \to y$ x \rightarrow y represents the bitwise THEN operation on two $30$ -bit numbers. Refer to the note for a detailed explanation of this operation.

Input

The first line contains a single integer $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^5), representing the number of people in the tree. The following $n$ lines describe each person. The $i$ -th line contains two integers $t_{i}$ t_i and $r_{i}$ r_i ( $0 \leq t_{i} \leq 1 0^{9}$ 0 \leq t_i \leq 10^9, $0 \leq r_{i} \leq n$ 0 \leq r_i \leq n), where $t_{i}$ t_i is the horse type of person $i$ , and $r_{i}$ r_i is the number of their direct ancestor, or $0$ if they have none.

The next line contains a single integer $m$ ( $1 \leq m \leq 1 0^{5}$ 1 \leq m \leq 10^5), the number of Polycarp's queries. The subsequent $m$ lines each contain a pair of integers $v_{i}, k_{i}$ v_i, k_i ( $1 \leq v_{i}, k_{i} \leq n$ 1 \leq v_i, k_i \leq n).

It is guaranteed that the family connections do not form cycles.

Output

Output $m$ integers, separated by spaces, corresponding to the answers for Polycarp's queries, in the order they appear in the input.

Examples

Example 1

Note

The result of the bitwise THEN operation on two $30$ -bit numbers is a $30$ -bit number, where each bit is determined by the bitwise THEN operation on the corresponding bits of the operands. Specifically,

10 \to 32 = 1073741813.

10 \rightarrow 32 = 1073741813.

The truth table for the THEN operation on bits is as follows:

$0 \to 0 = 1$ 0 \rightarrow 0 = 1;
$0 \to 1 = 1$ 0 \rightarrow 1 = 1;
$1 \to 0 = 0$ 1 \rightarrow 0 = 0;
$1 \to 1 = 1$ 1 \rightarrow 1 = 1.