There is a tree rooted at $1$ with $n$ nodes. The parent of node $i$ is $fa_i$ ($fa_i < i$), and the edge weight is $w_i$.

Each node has a villager, and all villagers are farmers. The villager at node $i$ has two attributes $a_i$ and $b_i$, meaning that to obtain one emerald from this villager, one must pay $a_i$ units of wheat, and the maximum number of emeralds that can be traded with this villager is $b_i$.

There are $q$ queries. Each query provides two integers $x$ and $y$, representing a traveling merchant who arrives at node $x$ to purchase emeralds. The merchant buys emeralds at a price of $y$ units of wheat per emerald, with no upper limit on the quantity.

To earn more wheat, for each query, you can open some roads within the subtree of $x$. Starting from $x$, you can travel through the opened roads to reach various nodes to purchase emeralds. Let $S$ be the set of opened roads. Opening these roads costs $\sum\limits_{i\in S} w_i$ emeralds. The final number of emeralds sold to the traveling merchant is the total number of emeralds purchased minus the number of emeralds spent on opening the roads. The final profit is the wheat obtained from selling to the traveling merchant minus the total wheat spent on purchasing all the emeralds.

Each query is independent. You need to find the maximum profit for each query.

Since the traveling merchant's arrival is random, you can consider this problem to be forced online.

However, the arrival follows a certain pattern, so you can assume that the queried $x$ is monotonically non-increasing.

Input

The first line contains a positive integer $n$ ($1\leq n\leq 10^5$).

The second line contains $n$ integers, representing $a_1, a_2, \dots, a_n$.

The third line contains $n$ integers, representing $b_1, b_2, \dots, b_n$.

The next $n$ lines each contain two non-negative integers. The $i$-th line (for $i=1$ to $n$, where the first line of this block corresponds to node 2) contains $fa_i$ and $w_i$. (Note: The input format specifies lines 4 to $n+3$ contain $fa_i, w_i$ for $i=2 \dots n$).

The $(n+4)$-th line contains an integer $q$.

The next $q$ lines each contain two integers $x$ and $y'$. Each line describes a query.

The actual $y$ for the $i$-th query is $y' \operatorname{xor} lastans$, where $lastans$ is the answer to the $(i-1)$-th query. Specifically, for the first query, $lastans=0$.

It is guaranteed that the decrypted $x$ is monotonically non-increasing.

Output

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

Examples

Examples

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

Constraints

For $100\%$ of the data, $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$.

• Subtask 1 (20pts): $n, q\le 5000$;
• Subtask 2 (30pts): $x=1$ for all queries;
• Subtask 3 (25pts): The tree is a chain;
• Subtask 4 (25pts): No special restrictions.