F. Chippa Rank
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Chippi Chappa wants to become an uma, but needs to figure out how well he will do first. There will be $$$n$$$ other umas in this race on a track of length $$$d$$$. The $$$i$$$th uma will have a starting placement of $$$a_i$$$ $$$(1 \le a_i \le n,$$$ $$$a$$$ is a permutation of $$$1$$$ through $$$n)$$$ and a speed of $$$s_i$$$. If an uma starts at position $$$a_i$$$, it is distance $$$a_i$$$ from the start of the track initially, so it must travel a total distance of $$$d + a_i$$$ in the race. Answer $$$q$$$ queries from Chippi Chappa, each consisting of an integer $$$g$$$. Given that Chippi Chappa starts at place $$$n+1$$$, for each query, find Chippi Chappa's finishing rank if he has a speed of $$$g$$$.

Input

The first line of input will contain $$$3$$$ space-separated integers $$$n$$$, $$$q$$$, and $$$d$$$ $$$(1 \le n, q, d \le 2\cdot 10^5)$$$ — the number of umas, the number of queries, and the track length.

The second line of input will contain $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le n)$$$ — a permutation of $$$1$$$ through $$$n$$$, giving the starting placements of the standard umas.

The third line of input will contain $$$n$$$ space-separated integers $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \le s_i \le 10^9)$$$ — the speed of each uma.

Each of the next $$$q$$$ lines contains a single integer $$$g_i$$$ $$$(1 \le g_i \le 10^9)$$$ — the speed of Chippi Chappa in the $$$i$$$th query.

Output

Output $$$q$$$ lines. The $$$i$$$th line should contain a single integer — Chippi Chappa's finishing rank (1 denotes first place) if his speed is $$$g_i$$$. It is guaranteed that there are no ties: no two standard umas tie with each other, and Chippi Chappa does not tie any uma in any query.

Examples
Input
1 1 5
1
2
3
Output
1
Input
4 4 12
1 2 3 4
5 7 4 6
3
5
8
10
Output
5
4
2
1
Note

In the first sample, the only standard uma starts a distance of 1 from the track, so she must run 6 units at a speed of 2 units per second = 6 / 2 = 3 seconds, while Chippi Chappa must run 7 units at a speed of 3 units per second = 7 / 3 = 2.333 seconds. So Chippi Chappa would win the race, and be at rank 1.