Under construction

Still being built. Things may change

Flappy Bird Scoring

Interview

Time limit1sMemory limit512 MB

Summary
Given each obstacle's gap A_i minus B_i, find for each bird size w how many obstacles it passes before meeting a gap smaller than w.
Level

Easy3 of 10

Topics
Array, Binary search
Solved
No attempts yet

Problem

Flappy Bird is a game where you dodge obstacles and travel as far as possible.

Each obstacle you dodge earns 1 point. The game has NN obstacles in total, and the ii-th obstacle is made of two obstacles. The top obstacle ends at position AiA_i, and the bottom obstacle ends at position BiB_i.

Sejeong, a Flappy Bird expert, can steer the bird to dodge the obstacles no matter how they are placed. (However, if the bird is larger than the gap between the obstacles, Sejeong cannot dodge them either.) That is, if the bird's size ww is larger than the gap of an obstacle, the bird cannot pass it. When the bird fails to pass an obstacle, the game ends immediately.

Several kinds of birds are given, one game each. For each bird, find how many points it can earn.

Print Sejeong's game score.

Input

The first line contains the number of obstacles NN. (1≤N≤250 000)(1 \le N \le 250\ 000)

The second line contains the top obstacle positions AiA_i, separated by spaces. (−109≤Ai≤109)(-10^9 \le A_i \le 10^9)

The third line contains the bottom obstacle positions BiB_i, separated by spaces. (−109≤Bi≤109)(-10^9 \le B_i \le 10^9) (The input is guaranteed to satisfy Bi≤AiB_i \le A_i.)

The fourth line contains the number of birds QQ to play. (1≤Q≤250,000)(1 \le Q \le 250,000)

The fifth line contains the size wiw_i of each bird. (1≤wi≤109)(1 \le w_i \le 10^9)

Output

For each bird, print the maximum game score Sejeong can earn, one score per line.

Examples1

  1. Example 1

    Input
    7
10 5 7 7 8 9 10
1 -1 2 -1 5 2 9
4
3 7 5 1
    Expected output
    6
1
4
7