给定一棵节点数为 $N$ 的有根树，其中 $1$ 号点是根节点，除此之外第 $i$ 个节点的父亲为 $f_i$。每个节点有一个权值 $A_i$，所有边权均为 $1$。

给定 $Q$ 个询问，每个询问以一个二元组 $(x, k)$ 的形式给出，表示询问以 $x$ 为根的子树内，与 $x$ 距离至少为 $k$ 的所有节点权值之和。

由于输出量可能过大，我们使用以下方式减少输出量。

void print(int q, long long* ans, int lim) {
    for(int i = 1; i <= q; ) {
        long long res = 0;
        for(int j = i; j <= min(q, i + lim - 1); j++) res ^= ans[j];
        i += lim;
        printf("%lld\n", res);
    }
    return ;
}

程序中 $ans_i$ 表示第 $i$ 次询问的答案，你需要在你的程序末尾调用以上函数来输出答案。

输入格式

第一行为一个正整数 $N$。

第二行为 $N$ 个正整数 $A_i$。

第三行为 $N - 1$ 个正整数 $f_i$，第 $i$ 个正整数表示 $i + 1$ 的父亲节点。

第四行为一个正整数 $Q$。

接下来 $Q$ 行每行两个整数 $x、k$。

最后一行为一个正整数 $lim$。

输出格式

在你的程序末尾调用以上函数来输出答案。

样例

input

7
1 2 3 4 5 6 7
1 1 2 2 3 3
5
2 0
2 1
6 1
6 0
1 1
1

output

11
9
0
6
27

限制与约定

对于 $20\texttt{%}$ 的数据，$1 \leq N, Q \leq 2501$

对于 $70\texttt{%}$ 的数据，$1 \leq N, Q \leq 252501$

对于 $100\texttt{%}$ 的数据，$1 \leq N, Q \leq 2525010$，$1 \leq A_i \leq 52501$，$1 \leq f_i \leq i - 1$，$1 \leq x, k + 1, lim \leq N$

保证单个输出文件大小不超过 $0.5\texttt{MB}$，但如果你需要使用Hack功能，请保证$ Max(1,floor(N/10000)) \leq lim$。

时间限制：$2\texttt{s}$

空间限制：$256\texttt{MB}$