小 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。