题目描述

Algosia 有一块 $n \times m$ 的矩形棋盘，分为 $n \cdot m$ 个方格。她喜欢在棋盘上摆放立方积木玩耍。积木的大小正好和方格一样，所以她总是把积木摆得刚好占满一个格子。

玩完后，Algosia 会乖乖收拾积木。她的手很小，一次只能从棋盘上拿一个积木放进盒子。要拿起积木，她得用手指夹住它的两个相对面，这两个面还不能被旁边的积木挡住。换句话说，能拿起的积木要么左右两边没邻居，要么上下两边没邻居。

今天她开始玩时，棋盘上已经放了 $k$ 个积木。接着，在父母的帮助下，她进行了 $q$ 次操作，每次在棋盘上放一个积木或取下一个积木（父母帮忙时，即使积木被邻居挡住也能取下）。

Algosia 想知道，每种积木摆放状态下（包括开始时和每次操作后），她最多能独立地、一个接一个地拿走多少积木。她只是假设性地思考，不会真的去拿。请你写一个程序，算出每种状态下的答案。

输入格式

输入的第一行包含四个整数 $n$, $m$, $k$, $q$ ($1 \leq n, m \leq 200000$, $1 \leq k, q \leq 75000$)，分别表示棋盘的高和宽、初始积木数量以及操作次数。

接下来的 $k$ 行，每行包含两个整数 $x_i$, $y_i$ ($1 \leq x_i \leq n$, $1 \leq y_i \leq m$)，表示初始时第 $i$ 个积木所在格子的坐标。没有格子会同时有多个积木。

接下来的 $q$ 行，每行包含两个整数 $x_j$, $y_j$ ($1 \leq x_j \leq n$, $1 \leq y_j \leq m$)，表示第 $j$ 次操作的格子坐标。如果该格子原来没积木，这次操作是放一个积木；如果已有积木，这次操作是取走它。

输出格式

输出 $q+1$ 行，每行一个整数。第 $i$ 行的数字表示在执行前 $i-1$ 次操作后的积木状态下，Algosia 能独立地、一个接一个拿走的积木数量。

样例

输入：

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

输出：

22
14
6
5

样例说明

• 图 1：这是游戏开始时的棋盘状态，上面有 $k=22$ 个积木。Algosia 可以立刻拿走其中 14 个。

• 图 2：这是拿走那 14 个积木后的棋盘状态。所有剩下的积木，小阿戈西亚也能轻松拿走。因此，在初始配置下，小阿戈西亚可以清理全部 22 个积木。

• 图 3：在第一次操作中，Algosia 添加了一个标红的积木，形成一个 $3 \times 3$ 的方块，她无法以任何方式取下这个方块。其余的积木（共 14 个）是可以清理的。

• 图 4：这是第二次操作后的棋盘状态。Algosia 只能拿走 6 个积木。

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

数据范围与提示

在某些子任务中，额外满足 $q=1$。