K. Keen Coal Extraction
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

The mining site consists of several mine shafts interconnected by tunnels. Any two mine shafts are connected by a unique sequence of tunnels. For each shaft, the amount of coal extracted in tons is known.

Miners establish a camp in a certain shaft and can extract coal either at the camp or in shafts located below the camp within a distance of no more than $$$H$$$ tunnels. Miners are not allowed to travel upwards through the tunnels due to technological constraints related to pressure.

It's only sensible to establish a camp if it is possible to extract at least $$$S$$$ tons of coal.

You need to minimize the maximum distance $$$H$$$ from the camp given that the camp is located in shaft $$$V$$$ and the total extraction is at least $$$S$$$ tons of coal.

Input

The first line of input contains an integer $$$N$$$ ($$$2 \leq N \leq 80\,000$$$) — the number of mine shafts. The second line contains $$$N$$$ integers $$$M_i$$$ ($$$0 \leq M_i \leq 10\,000$$$) — the amount of coal extracted in shaft $$$i$$$. The third line provides $$$N - 1$$$ integers $$$E_i$$$ ($$$1 \leq E_i \leq N$$$) — the index of the shaft connected by a tunnel to shaft $$$i + 1$$$, where shaft $$$E_i$$$ is situated above shaft $$$i + 1$$$. Shaft $$$1$$$ is positioned above all the others.

The fourth line contains a single integer $$$Q$$$ ($$$1 \leq Q \leq 125\,000$$$) — the number of queries. The following $$$Q$$$ lines describe the queries. Each query consists of two integers $$$V$$$ and $$$S$$$ ($$$1 \leq V \leq N$$$, $$$1 \leq S \leq 10^9$$$) —- the number of the shaft where the camp is located, and the minimum amount of coal in tons.

Output

For each query, output a single line containing the number that equals the minimum distance to which the miners can extract from the camp to obtain at least the specified amount of tons of coal, or «$$$-1$$$» if it is impossible.

Interaction

First, the jury program outputs the layout of the mine and the number of queries. Then, the jury program issues one query at a time.

Each subsequent query will be sent to the input stream only after the participant's program has responded to the current query.

Example
Input
4
2 0 2 2
1 2 2
4
3 2
2 3
4 3
2 9
Output
0
1
-1
-1