Background

Justin was playing with his board and pieces... Suddenly, he came up with a very interesting game.

Problem Description

The board can be seen as an $N \times M$ grid. Because Justin is too strong, he broke $T$ cells, meaning no piece can be placed on those cells.

The game Justin came up with works like this: At the beginning, you may choose some unbroken cells in the first column and place one piece on each of them. Then, you may perform the following operations in order any number of times:

1. Choose one piece and move it up or down to an adjacent cell that is unbroken and does not contain any other piece.

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

Justin now gives you $Q$ queries. Each time you are given a $k_i$, asking: what is the maximum number of pieces you can place in the first column such that, after some operations, you can move all pieces to the last column, and the total number of operation 1 performed by all pieces combined is at most $k_i$.

(Thanks to ywwywwyww for finding an issue in the statement. It 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$, indicating a broken cell.

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

Output Format

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

3 5 2 3
1 2
2 4
0
1
2

1
2
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

0
0
0
0
0
0
0
0
0
0

Hint

In the first sample:

When the limit is $0$, you can place one piece at $(3,1)$, then keep performing operation 2.

When the limit is $1$, you can place one piece at $(3,1)$ and another at $(2,1)$. After performing operation 2 twice, perform operation 1 once on the piece at $(2,3)$ to move it to $(1,3)$, then keep performing operation 2.

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

In the second sample:

You can see it is completely blocked, so it is impossible to move to the last column.

Constraints:

Test Point ID	$N\le$	$M\le$	$T\le$	$Q\le$
$1$		$10^6$	$1$	$10^5$
$2-6$	$10$	$100$	$10$	$100$
$7-10$	$20$		$50$	$10^3$
$11-14$	$30$	$10^4$	$100$	$10^4$
$15-20$	$50$	$10^6$	$10^3$	$10^5$

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

The testdata for test points $11$~$20$ is randomly generated.

Translated by ChatGPT 5