Roger is going to a hackathon again! Unlike last time, he has prepared a possible list of projects and has an estimate of how long each project takes, as well as its wow factor. However, his partner, Joey, wishes to go for very long coffee breaks, and thus gives him ~Q~ queries to answer: if they only have ~T~ minutes to complete their project, what is the maximum wow factor of their project.

Note: at hackathons (or at least the ones in this question), only a single project is done.

Constraints

For all subtasks:

~1 \le t_i, w_i, T \le 10^6~

Subtask 1 [60%]

~1 \le N, Q \le 10^3~

Subtask 2 [40%]

~1 \le N, Q \le 10^6~

Input Specification

Line ~1~: An integer, ~N~, the number of projects Roger has prepared.
Lines ~2 \dots N+1~: Two space separated integers, ~t_i~ and ~w_i~, the amount of time required for the ~i^{th}~ project and its wow factor respectively.
Line ~N+2~: An integer, ~Q~, the number of queries Joey gives.
Lines ~N+3 \dots N+Q+2~: An integer, ~T~, the maximum time Roger and Joey have.

Output Specification

~Q~ space-separated integers, the answer to each query.

Sample Input

3
1 3
8 9
2 2
3
10
8
3

Sample Output

9
9
3

Explanation for Sample Output

If Roger and Joey have ~10~ minutes, they have enough time to complete projects ~1~, ~2~, and ~3~, and the maximum wow factor is ~9~.
If they have ~8~ minutes, they still have time to complete all three projects, so the maximum wow factor is still ~9~.
If they have ~3~ minutes, they can only complete projects ~1~ and ~3~, and the maximum wow factor of these two projects is ~3~.