Blood Brothers Strike Back

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. 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, 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)-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).

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, k_i. Your task is to determine the horse value of the set of k_i-sons of the person numbered v_i for each pair v_i, k_i.

The horse value of a set of people p_1, p_2, ..., p_r (p_1 < p_2 < ... < p_r) is calculated as (p_1 → (p_2 → (... → p_r))). If the set is empty, the horse value is zero. The operation x → 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 of input contains a single integer n (1 ≤ n ≤ 10^5), representing the number of people in the village. The following n lines describe each person. The i-th line contains two integers t_i and r_i (0 ≤ t_i ≤ 10^9, 0 ≤ r_i ≤ n), where t_i is the horse type of person i, and r_i is the number of their direct ancestor, or 0 if they have none.

The next line contains a single integer m (1 ≤ m ≤ 10^5), the number of Polycarp's queries. The subsequent m lines each contain a pair of integers v_i, k_i (1 ≤ v_i, k_i ≤ 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

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 → 32 = 1073741813.

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

• 0 → 0 = 1;

• 0 → 1 = 1;

• 1 → 0 = 0;

• 1 → 1 = 1.