Bandits in the Tree

Input

The first line contains a single integer $n$ (2 \leq n \leq 10^5) — the number of cities.

Each of the next (n - 1) lines contains two integers p_i and d_i (1 \leq p_i < i, 1 \leq d_i \leq 10^3), indicating a road between cities $i$ and p_i with a length of d_i. Indexing starts from $2$.

The following line contains $n$ integers a_i (1 \leq a_i \leq n), representing the clans that captured each city.

The next line contains $n$ integers t_i (1 \leq t_i \leq 10^9), representing the capture times for each city.

The next line contains a single integer $m$ (1 \leq m \leq 10^5) — the number of queries.

The last $m$ lines describe the queries. Each line contains four integers u_i, v_i, b_i, T_i (1 \leq u_i, v_i, b_i \leq n, 1 \leq T_i \leq 10^9) — the starting and ending cities of the path, the traveler's clan number, and the start time of the journey, respectively.

Output

For each query, output a single integer on a separate line — the number of the first city on the path from $u$ to $v$ that cannot be traversed. If all cities on the path can be traversed, output «-1».

Note the large volume of input and output data in this problem. It is recommended to use fast input and output methods, such as scanf/printf instead of cin/cout in C++, and sys.stdin.readline instead of input in Python. It is also recommended to use the PyPy interpreter when solving problems in Python.

Examples

Scoring

1. ($7$ points): p_i = 1;

2. ($9$ points): n, m \leq 10^3;

3. ($11$ points): p_i = i - 1, t_i = 1;

4. ($18$ points): p_i = i - 1, a_i = 1, b_i = 2;

5. ($15$ points): p_i = i - 1;

6. ($11$ points): t_i = 1;

7. ($17$ points): a_i = 1, b_i = 2;

8. ($12$ points): no additional constraints.