Bandits in the Tree

There are $n$ cities, numbered from $1$ to $n$. These cities are interconnected by $(n-1)$ roads, ensuring that any city can be reached from any other city. Each road has a specific length.

It is known that city $i$ was captured by the bandit clan numbered $a_i$ ($1\le a_i\le n$) at time $t_i$. From the moment city $i$ is captured (i.e., starting at time $t_i$ inclusive), only representatives of clan $a_i$ are allowed to pass through it.

You need to answer $m$ queries of the following type:

• u v b T — Determine if a representative of clan $b$ can travel from city $u$ to city $v$ starting at time $T$. If the journey is not possible, identify the first city on the path from $u$ to $v$ that cannot be traversed.

Input

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

Each of the next $(n-1)$ lines contains two integers $p_i$ and $d_i$ ($1\le p_i<i$, $1\le d_i\le 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\le a_i\le n$), representing the clans that captured each city.

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

The next line contains a single integer $m$ ($1\le m\le 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\le u_i,v_i,b_i\le n$, $1\le T_i\le 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\le 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.