Problem Background

Justin is fiddling with his chessboard and pieces... suddenly, he comes up with a very fun game.

Problem Description

The chessboard can be seen as an $N \times M$ grid, due to Justin being too strong, so he has damaged $T$ squares. This means that pieces cannot be placed on these squares.

The game Justin thought of is as follows: Initially, you can choose some undamaged squares in the first column of the chessboard and place a piece on each of them. Then, you can perform the following operations multiple times:

1. Select a piece and move it up or down to an adjacent good square that does not have another piece on it.

2. Move all pieces to the next column. If any piece lands on a damaged square after moving to the next column, this operation cannot be performed.

Justin now gives you $Q$ questions, each providing a $k_i$, asking you the maximum number of pieces you can place in the first column such that after several operations, you can move all pieces to the last column, and the total number of times operation 1 is performed does not exceed $k_i$.

(Thanks to the expert ywwywwyww for discovering the problem issue, which has now been fixed.)

Input Format

The first line contains four positive integers: $N$, $M$, $T$, $Q$.

The next $T$ lines each contain two positive integers $x_i$, $y_i$ representing a damaged square.

The next $Q$ lines each contain one positive integer $k_i$ representing Justin's query.

Output Format

Output $Q$ lines, each containing a non-negative integer representing the answer to each query.

Sample Input and Output

Sample Input #1

3 5 2 3
1 2
2 4
0
1
2

Sample Output #1

1
2
2

Sample Input #2

5 1000 5 10
1 2
2 3
3 4
4 5
5 6
0
1
2
3
4
5
6
7
8
9

Sample Output #2

0
0
0
0
0
0
0
0
0
0

Notes

For the first sample: When the limit is 0, you can place one piece at (3,1) and then continuously perform operation 2.

When the limit is 1, you can place one piece at (3,1) and one at (2,1), then perform operation 2 twice, move the piece at (2,3) once to (1,3) with operation 1, and then continuously perform operation 2.

When the limit is 2, it is the same as above. Because if you place three pieces, you cannot perform operation 2.

For the second sample: It is completely blocked, so it is impossible to move to the last column.

Data Range:

$$1 \le x_i \le N \qquad 1 \le y_i \le M \qquad 0 \le k_i \le 2^{31}-1$$

The data for test points 11 to 20 are randomly generated.

见题面 Input 部分

见题面 Output 部分