Collecting Bricks

You are given an n × m rectangular board divided into n × m unit cells. There are several bricks placed on the board; each brick exactly occupies one cell. We denote the cell in the i-th row and j-th column by (i,j).

A brick can be "collected" (i.e. removed) if and only if it satisfies one of the following conditions at the time it is collected:

• Vertical condition: The cell immediately above and the cell immediately below do not contain a brick. (Note that if a neighbor cell is outside the board, it is considered empty.)
• Horizontal condition: The cell immediately to the left and the cell immediately to the right do not contain a brick.

Initially there are k bricks on the board. Then there are q operations. In each operation, a brick is either added to an empty cell or removed from a cell (removals in the operations are not subject to the above conditions). For i = 1,2,…,q+1, Algosia wants to know: after performing the first i − 1 operations, what is the maximum number of bricks that can be collected one‐by‐one (in some order) by following the collection rule described above? Note that when bricks are hypothetically collected they are not actually removed from the board.

Observation: A brick’s ability to be collected depends only on its immediate neighbors. In particular, a brick at cell (r, c) is collectible if and only if at the time of removal at least one of the following holds:

• Vertical: r == 1 or (r-1, c) is empty, and r == n or (r+1, c) is empty.
• Horizontal: c == 1 or (r, c-1) is empty, and c == m or (r, c+1) is empty.

Your task is to process the operations sequentially. After each update (including the initial board state before any operations), compute the maximum number of bricks that can be collected by choosing an appropriate order of collection.

inputFormat

The first line of input contains four integers: n, m, k and q — the number of rows, the number of columns, the initial number of bricks, and the number of operations.

The next k lines each contain two integers r and c, representing that there is initially a brick at cell (r, c).

The following q lines each describe an operation in one of the following two formats:

• add r c — add a brick at cell (r, c) (it is guaranteed that this cell is empty when the operation is executed).
• remove r c — remove the brick from cell (r, c) (it is guaranteed that there is a brick at this cell).

It is guaranteed that all operations are valid.

outputFormat

Output q+1 lines. The i-th line (for i = 1, 2, …, q+1) should contain a single integer — the maximum number of bricks that can be collected by following the removal rule after performing the first i - 1 operations.

sample

3 3 1 2
2 2
add 1 1
remove 2 2

1
2
1

</p>