Given a rooted tree $T$ with $n$ nodes, where nodes are numbered starting from 1 and the root is node 1. Each node has a positive integer weight $v_i$.

There are $Q$ queries. For each query, given $(x, k)$, let $c_1, c_2, \dots, c_m$ be the indices of all nodes in the subtree of node $x$ (including $x$ itself) such that the distance from node $x$ to the node is at most $k$. The answer to this query is:

$$(v_{c_1} \oplus d(c_1, x)) + (v_{c_2} \oplus d(c_2, x)) + \dots + (v_{c_m} \oplus d(c_m, x))$$

Where $d(x, y)$ denotes the number of edges on the unique simple path between node $x$ and node $y$ in the tree, and $d(x, x) = 0$. $\oplus$ denotes the bitwise XOR operation.

Input

The first line contains an integer $n$, representing the size of the tree. The second line contains $n$ integers, representing $v_i$. The third line contains $n - 1$ integers, representing the parent $p_i$ of nodes 2 through $n$, respectively. The fourth line contains an integer $Q$. The following $Q$ lines each contain two integers $x, k$, representing a query $(x, k)$.

Output

Output $Q$ lines, where the $i$-th line contains an integer representing the answer to the $i$-th query.

Constraints

• For 10% of the data, $n, Q \le 2 \times 10^3$.
• For 20% of the data, $n, Q \le 10^5$.
• For another 20% of the data, $p_i = i - 1$.
• For another 10% of the data, $k \le 20$.
• For another 20% of the data, $k = n$.
• For another 10% of the data, $v_i = 0$.
• For 100% of the data, $1 \le n, Q \le 10^6$, $0 \le v \le 10^9$, $1 \le p_i < i$, $1 \le x, k \le n$.

Examples

Input 1

10
9 3 0 7 4 8 8 7 2 5
1 1 2 2 3 6 6 8 7
10
8 2
2 1
5 1
4 1
4 1
1 4
4 1
6 3
4 1
1 4

Output 1

10
14
4
7
7
55
7
30
7
55