Little Algosia has a rectangular board of dimensions $n \times m$, divided into $n \cdot m$ square fields. Algosia likes to play by arranging cubic blocks on the board. The dimensions of the blocks are the same as the sizes of the fields, so Algosia always places the blocks such that they occupy exactly one field.

After finishing the game, Algosia always tidies up the blocks neatly. She has small hands, so in one move she is able to move only one block from the board to a box. To be able to grab a block, she must be able to grasp it with her fingers by two opposite walls, and these walls cannot be covered by adjacent blocks. In other words, such a block must either have no neighbors on the left and right, or it must have no neighbors above and below.

Algosia started today's game with a board on which $k$ blocks were placed. Then, with the help of her parents, she added or removed a single block from the board $q$ times (thanks to the help of her parents, it was possible to remove a block even if it had its walls blocked by adjacent blocks).

The girl wonders, for each configuration of blocks on the board (i.e., at the beginning of the game and after each of the $q$ moves), how many blocks at most she could, one by one, independently remove from the board. Algosia considers this only hypothetically – she does not actually remove these blocks. Write a program that will determine these numbers for each configuration.

Input

The first line contains four integers $n, m, k, q$ ($1 \le n, m \le 200\,000$, $1 \le k, q \le 75\,000$), representing the height and width of the board, the number of blocks placed on the board at the beginning of the game, and the number of moves performed, respectively.

The next $k$ lines contain two integers $x_i, y_i$ ($1 \le x_i \le n, 1 \le y_i \le m$), representing the coordinates of the field on which the $i$-th block stands at the beginning of the game. No more than one block stands on any field.

The next $q$ lines contain two integers $x_j, y_j$ ($1 \le x_j \le n, 1 \le y_j \le m$), representing the coordinates of the field on which the $j$-th move was performed. If there was no block on this field, the move consisted of adding a block there. If a block was already standing on this field, the move consisted of removing it.

Output

The output should contain $q + 1$ lines, each containing a single integer. The number in the $i$-th line should be equal to the number of blocks that Algosia can independently, one by one, collect from the board if we consider the configuration of blocks after performing the first $i - 1$ moves.

Subtasks

In tests worth a certain non-zero number of points, the condition $q = 1$ holds.

Examples

Input 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

Output 1

22
14
6
5

Note

Figure 1: This is what the board looks like at the beginning of the game. There are $k = 22$ blocks on it. Algosia can immediately remove 14 of them from the board.

Figure 2: This is what the board looks like after removing those 14 blocks. Algosia can also easily remove all the remaining blocks. Thus, in the first configuration, Algosia is able to clean up all 22 blocks.

Figure 3: In the first move, Algosia adds the block marked in red, creating a $3 \times 3$ square, which she will not be able to remove in any way. The remaining blocks (there are 14 of them) are possible to clean up.

Figure 4: This is what the board looks like after the second move. Algosia can only remove 6 blocks.

Figure 5: This is what the board looks like after the third move. The answer is 5.