题目背景

Justin摆弄着他的棋盘和棋...突然，他想到了一个非常好玩的游戏。

题目描述

棋盘可以看做是一个$N \times M$的网格，~~由于Justin太健壮了，~~所以他把$T$个格子弄坏了。也就是说，上面没法放棋子。

Justin想到的游戏是这样的：一开始，你可以选择棋盘的第一列的一些没有坏的格子，在上面各放上一枚棋子。然后，你可以执行依次以下操作若干次：

1. 选择一枚棋子，将其向上或者向下移动到相邻的一个好的且没有其他棋子的格子上。

2. 将所有棋子移动到下一列。若移动到下一列后有任意一个棋子落在坏的格子上，则不能执行此操作。

Justin现在给了你$Q$个问题，每一次给你一个$k_i$，询问你最多能在第一列上放多少枚棋子使得经过若干次操作后你能将所有棋子移动到最后一列，且所有棋子加起来最多执行$k_i$次1操作。

(感谢巨佬ywwywwyww 发现题目问题，现已修复。)

输入格式

第一行四个正整数:$N$,$M$,$T$,$Q$

接下来$T$行每行两个正整数$x_i$,$y_i$表示一个坏了的格子。

接下来$Q$行每行一个正整数$k_i$表示第$i$次Justin的询问。

输出格式

输出$Q$行，每行一个非负整数表示每一次询问的答案。

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

提示

第一组样例：限制为0时，可以在(3,1)放置一枚棋子，然后一直执行二操作。

限制为1时，可以在(3,1)放置一枚棋子，在(2,1)放置一枚棋子，然后执行两次二操作之后对(2,3)上的棋子执行一次一操作到(1,3)，然后一直执行二操作就好了。

限制为2时，和上面一样。因为如果放置三枚棋子的话是没办法执行操作二的。

第二组样例：发现完全堵死了，所以根本不可能移动到最后一列。

数据范围：

测试点编号	$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 $$

此题测试点$11$~$20$的数据随机生成。