小さなアルゴシアは、$n \times m$ の長方形の盤面を持っており、これは $n \cdot m$ 個の正方形のマスに分割されています。アルゴシアは盤面の上に立方体のブロックを並べて遊ぶのが好きです。ブロックの寸法はマスのサイズと同じであるため、アルゴシアは常にブロックがちょうど1つのマスを占めるように置きます。

遊びが終わると、アルゴシアはいつもきれいにブロックを片付けます。彼女の手は小さいため、1回の動作で盤面から箱へブロックを1つしか運ぶことができません。ブロックをつかむためには、指でブロックの向かい合う2つの面をつかむ必要があり、それらの面は隣接するブロックによって覆われていてはいけません。言い換えれば、そのようなブロックは、左右に隣接するブロックがないか、あるいは上下に隣接するブロックがないかのどちらかでなければなりません。

アルゴシアは今日、$k$ 個のブロックが置かれた盤面で遊び始めました。その後、両親の助けを借りて、$q$ 回、盤面にブロックを1つ追加するか、盤面からブロックを1つ取り除きました（両親の助けがあれば、隣接するブロックによって面が塞がれていてもブロックを取り除くことが可能でした）。

彼女は、盤面上のブロックの各構成（遊びの開始時および $q$ 回の各動作の後）について、最大で何個のブロックを、1つずつ、自分自身の手で盤面から取り除くことができるかを考えています。アルゴシアはこれを仮定として考えているだけで、実際にはこれらのブロックを取り除いているわけではありません。各構成に対してこれらの数を求めるプログラムを作成してください。

入力

最初の行には、4つの整数 $n, m, k, q$ ($1 \le n, m \le 200\,000, 1 \le k, q \le 75\,000$) が含まれており、それぞれ盤面の高さと幅、遊び開始時に盤面に置かれているブロックの数、および実行された動作の数を表します。

続く $k$ 行には、それぞれ2つの整数 $x_i, y_i$ ($1 \le x_i \le n, 1 \le y_i \le m$) が含まれており、遊び開始時に $i$ 番目のブロックが置かれているマスの座標を表します。どのマスにも複数のブロックは置かれていません。

続く $q$ 行には、それぞれ2つの整数 $x_j, y_j$ ($1 \le x_j \le n, 1 \le y_j \le m$) が含まれており、$j$ 番目の動作が行われたマスの座標を表します。そのマスにブロックがなかった場合、その動作はそこにブロックを追加するものでした。一方、そのマスにすでにブロックがあった場合、その動作はそれを取り除くものでした。

出力

出力には、$q + 1$ 行の整数を出力する必要があります。$i$ 行目の数は、最初の $i - 1$ 回の動作を実行した後のブロックの構成を考えた場合に、アルゴシアが自分自身の手で1つずつ盤面から取り除くことができるブロックの数と等しくなければなりません。

制約

ある程度の点数が与えられるテストケースでは、$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$ 個のブロックがあります。アルゴシアはすぐにそのうち14個を取り除くことができます。

図2: これらの14個のブロックを取り除いた後の盤面の様子。残りのすべてのブロックもアルゴシアは問題なく取り除くことができます。したがって、最初の構成ではアルゴシアは22個すべてのブロックを片付けることができます。

図3: 最初の動作で、アルゴシアは赤色で示されたブロックを追加し、$3 \times 3$ の正方形を作りました。これはどのようにも取り除くことができません。残りのブロック（14個）は片付け可能です。

図4: 2回目の動作後の盤面の様子。アルゴシアは6個のブロックしか取り除くことができません。

図5: 3回目の動作後の盤面の様子。答えは5です。