有一棵以 $1$ 为根大小为 $n$ 的树，编号为 $i$ 的点的父亲是 $fa_i(fa_i < i)$，边权为 $w_i$。

每个节点上有一个村民，这个村民的职业均为农民。在编号为 $i$ 的节点上的村民有两个属性 $a_i$ 和 $b_i$，表示在该村民这交易得到一个绿宝石需要支付给他 $a_i$ 份小麦，以及在该村民这最多只能交易 $b_i$ 个绿宝石。

现在有 $q$ 次询问，第 $i$ 次询问会给出一个整数 $x,y$，表示有一个流浪商人来到了节点 $x$ 收购绿宝石，且该商人收购绿宝石的价格为 $y$ 份小麦，收购数量无上限。

为了赚取更多的小麦，对于每次询问你可以开通 $x$ 子树内的一些道路，然后从 $x$ 出发通过开通的道路到达一些节点购买绿宝石，令 $S$ 表示开通的道路集合，则开通这些道路需要花费 $\sum\limits_{i\in S} w_i$ 个绿宝石，最后能出售给流浪商人的绿宝石数为购买的数量减去开通道路需要花费的数量，最终收益为出售给流浪商人能获得的小麦数减去购买所有绿宝石花费的小麦数。

每次询问是独立的，你需要对于每次询问求出能获得的最大小麦数。

由于流浪商人的刷新是随机的，所以你可以认为这个题是强制在线的。

但是这个刷新又是保证了某种规律，所以你可以认为保证询问的 $x$ 是单调不增。

输入格式

第一行一个正整数 $n$（$1\leq n\leq 10^5$）。

第二行 $n$ 个整数，表示 $a_1,a_2,\dots,a_n$。

第三行 $n$ 个整数，表示 $b_1,b_2,\dots,b_n$。

第四到 $n+3$ 行每行 $2$ 个非负整数，第 $i+2$ 行为 $fa_i, w_i$。

第 $n+4$ 行一个整数 $q$。

接下来 $q$ 行，每行两个整数 $x,y'$，描述了一次询问。

第 $i$ 次询问真正的 $y$ 为 $y' \operatorname{xor} lastans$，其中 $lastans$ 表示第 $i-1$ 次询问的答案，特别的，第 $1$ 次询问的 $lastans=0$。

保证解密出来的 $x$ 单调不增。

输出格式

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

样例

输入

6
4 6 4 5 5 3 
3 1 5 6 6 3 
1 4
2 3
2 2
1 4
3 3
5
6 6
5 14
3 11
3 12
2 7

输出

9
12
15
0
1

数据范围与约定

对于 $100\%$ 的数据，满足 $1\le n\le 10^5,\ 1\le a_i, w_i,b_i\le 10^6,\ 1\le q\le 10^6,\ 1\le x\le n,1\le y\le 10^6$。

• Subtask1 (20pts): $n,q\le 5000$；
• Subtask2 (30pts): 对于所有询问保证 $x=1$；
• Subtask3 (25pts): 保证树是一条链；
• Subtask4 (25pts): 无特殊限制。