小 Algosia 有一个 $n \times m$ 的矩形棋盘，被划分为 $n \cdot m$ 个方格。Algosia 喜欢在棋盘上摆放立方体积木。积木的尺寸与方格大小相同，因此 Algosia 总是将积木放置在恰好占据一个方格的位置。

游戏结束后，Algosia 总是会整齐地清理积木。她的手很小，所以一次只能从棋盘上移走一个积木放入盒子里。为了抓住积木，她必须能够用手指捏住积木的两个相对面，且这些面不能被相邻的积木遮挡。换句话说，这样的积木要么在左右两侧没有相邻的积木，要么在上下两侧没有相邻的积木。

Algosia 今天开始游戏时，棋盘上放置了 $k$ 个积木。随后，在父母的帮助下，她进行了 $q$ 次操作，每次在棋盘上放置或移走一个积木（得益于父母的帮助，即使积木的侧面被相邻积木挡住，也可以将其移走）。

女孩想知道，对于每一种棋盘上的积木配置（即游戏开始时以及每次操作后），她最多能依次自行从棋盘上移走多少个积木。Algosia 只是假设性地考虑这个问题——她并没有真正移走这些积木。请编写一个程序，计算每种配置下的这个数字。

输入格式

第一行包含四个整数 $n, m, k, q$ ($1 \le n, m \le 200\,000, 1 \le k, q \le 75\,000$)，分别表示棋盘的高度和宽度、游戏开始时棋盘上的积木数量以及执行的操作次数。

接下来的 $k$ 行，每行包含两个整数 $x_i, y_i$ ($1 \le x_i \le n, 1 \le y_i \le m$)，表示第 $i$ 个积木在游戏开始时的坐标。每个方格上最多只有一个积木。

接下来的 $q$ 行，每行包含两个整数 $x_j, y_j$ ($1 \le x_j \le n, 1 \le y_j \le m$)，表示第 $j$ 次操作的坐标。如果该方格上没有积木，则操作为放置一个积木；如果该方格上已经有积木，则操作为移走该积木。

输出格式

输出应包含 $q + 1$ 行，每行一个整数。第 $i$ 行的数字应等于在执行前 $i-1$ 次操作后的积木配置下，Algosia 可以依次自行从棋盘上移走的积木数量。

子任务

在分值不为零的测试用例中，满足条件 $q = 1$。

样例

输入 1

5 7 22 3
1 1
1 2
1 3
2 3
3 3
3 2
2 1
3 1
4 1
5 1
1 5
1 6
1 7
2 5
2 7
3 5
3 6
3 7
4 5
5 5
4 7
5 7
2 2
2 6
5 1

输出 1

22
14
6
5

说明

图 1：游戏开始时的棋盘。上面有 $k = 22$ 个积木。Algosia 可以立即从棋盘上移走其中的 14 个。

图 2：移走那 14 个积木后的棋盘。所有剩余的积木 Algosia 也可以轻松移走。因此，在第一种配置中，Algosia 可以清理掉所有 22 个积木。

图 3：在第一次操作中，Algosia 放置了红色的积木，形成了一个 $3 \times 3$ 的正方形，她将无法以任何方式移走它。其余的积木（共 14 个）是可以清理的。

图 4：第二次操作后的棋盘。Algosia 只能移走 6 个积木。

图 5：第三次操作后的棋盘。答案是 5。