Fountain Cascade

Consider a fountain composed of \(N\) circular disks numbered from 1 to \(N\) from top to bottom. The \(i\)th disk has a diameter \(D_i\) and capacity \(C_i\). When water in a disk exceeds its capacity, the excess water overflows downward until it reaches a disk whose radius (half of its diameter) is larger than that of the current disk. Formally, the water overflows from disk \(i\) to the first disk \(j\) (with \(j > i\)) satisfying \(D_j > D_i\). If no such disk exists, the water flows into an external pool (denoted by output 0).

You will be given \(Q\) independent queries. Each query is described as follows:

• Pour \(V_i\) units of water onto disk \(R_i\).

You need to simulate the process described below for each query:

1. Start at disk \(R_i\) with \(V_i\) units of water.
2. If the water amount is less than or equal to the disk's capacity \(C_{R_i}\), then the water stops there.
3. If it exceeds \(C_{R_i}\), the disk retains \(C_{R_i}\) units and the remaining water \(V_i - C_{R_i}\) flows to the next disk \(j\) (\(j > R_i\)) that satisfies \(D_j > D_{R_i}\). Apply the same process at disk \(j\) with the incoming water.
4. If at any step no such disk exists (i.e. no disk below has a larger diameter), the water flows into the pool, and the answer for that query is 0.

Output the index of the disk where the water finally stops, or 0 if it flows into the pool.

Note: Each query is independent and does not affect others.

inputFormat

The input consists of multiple lines:

1. The first line contains an integer \(N\) (the number of disks).
2. The second line contains \(N\) space-separated integers \(D_1, D_2, ..., D_N\) (the diameters of the disks).
3. The third line contains \(N\) space-separated integers \(C_1, C_2, ..., C_N\) (the capacities of the disks).
4. The fourth line contains an integer \(Q\) (the number of queries).
5. Each of the next \(Q\) lines contains two integers \(R_i\) and \(V_i\), representing a query: pouring \(V_i\) units of water onto disk \(R_i\).

outputFormat

For each query output a single integer in a separate line indicating the index of the disk at which the water stops, or 0 if the water flows into the pool.

sample

5
5 3 6 4 10
10 5 4 3 7
3
1 5
2 10
2 100

1
5
0