题目描述

给定一棵 $n$ 个结点的有根树 $T$，结点从 $1$ 开始编号，根结点为 $1$ 号结点，每个结点有一个正整数权值 $v_i$。

有 $Q$ 次询问，对于一次询问，给定 $(x, k)$，设 $x$ 号结点的子树内（包含 $x$ 自身）的所有满足距离 $x$ 号结点不超过 $k$ 的结点编号为 $c_1, c_2, \cdots, c_m$（注：原题中“$c_k$”应为笔误，此处修正为 $c_m$，表示符合条件的结点总数），则这次询问的答案为：

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

其中 $d(x, y)$ 表示树上 $x$ 号结点与 $y$ 号结点间唯一简单路径所包含的边数，$d(x, x) = 0$。$\oplus$ 表示异或运算。

输入格式

1. 第一行一个整数 $n$，表示树的大小。
2. 第二行 $n$ 个整数，表示 $v_1, v_2, \cdots, v_n$。
3. 第三行 $n - 1$ 个整数，依次表示 $2$ 号结点到 $n$ 号结点的父亲编号 $p_2, p_3, \cdots, p_n$（满足 $1 \leq p_i < i$）。
4. 第四行一个整数 $Q$，表示询问次数。
5. 接下来 $Q$ 行，每行两个整数 $x, k$，表示一组查询。

输出格式

输出共 $Q$ 行，第 $i$ 行一个整数，表示第 $i$ 次询问的答案。

样例

输入

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

输出

10
14
4
7
7
55
7
30
7
55

数据范围与提示

• 对于 $10\%$ 的数据，满足 $n, Q \leq 2 \times 10^3$。
• 对于 $20\%$ 的数据，满足 $n, Q \leq 10^5$。
• 对于另外 $20\%$ 的数据，满足 $p_i = i - 1$（树为链状）。
• 对于另外 $10\%$ 的数据，满足 $k \leq 20$。
• 对于另外 $20\%$ 的数据，满足 $k = n$（查询子树内所有结点）。
• 对于另外 $10\%$ 的数据，满足 $v_i = 0$。
• 对于 $100\%$ 的数据，满足 $1 \leq n, Q \leq 10^6$，$0 \leq v_i \leq 10^9$，$1 \leq p_i < i$，$1 \leq x, k \leq n$。