AT_abc406_d [ABC406D] Garbage Removal

$ H $ 行 $ W $ 列のマス目があり、上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i, j) $ と表記します。 マス目の上には $ N $ 個のゴミが落ちており、 $ i $ 番目のゴミはマス $ (X_i, Y_i) $ に落ちています。 $ Q $ 個のクエリが与えられるので、順に処理したときの各クエリの答えを求めてください。各クエリは、以下のいずれかです。 - タイプ $ 1 $ : `1 x` の形式で入力として与えられる。マス目の $ x $ 行目に落ちているゴミの個数を答えとして求める。その後、 $ x $ 行目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。 - タイプ $ 2 $ : `2 y` の形式で入力として与えられる。マス目の $ y $ 列目に落ちているゴミの個数を答えとして求める。その後、 $ y $ 列目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $ $ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $ ここで、 $ \text{query}_i $ は $ i $ 番目のクエリであり、以下のいずれかの形式で与えられる。 > $ 1 $ $ x $ > $ 2 $ $ y $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリの答えを出力せよ。

### Sample Explanation 1 はじめ、ゴミはマス $ (1, 2), (1, 3), (3, 4), (3, 1), (2, 2) $ に落ちています。 $ 1 $ 番目のクエリでは、 $ 1 $ 行目に落ちているゴミはマス $ (1, 2), (1, 3) $ に落ちているゴミの $ 2 $ つであるため答えは $ 2 $ となります。これらの $ 2 $ つのゴミは捨てられ、残ったゴミはマス $ (3, 4), (3, 1), (2, 2) $ に落ちているゴミです。 $ 2 $ 番目のクエリでは、 $ 2 $ 行目に落ちているゴミはマス $ (2, 2) $ にあるゴミの $ 1 $ つであるため答えは $ 1 $ となります。このゴミは捨てられ、残ったゴミはマス $ (3, 4), (3, 1) $ に落ちているゴミです。 $ 3 $ 番目のクエリでは、 $ 2 $ 列目に落ちているゴミは存在しないため答えは $ 0 $ となります。 $ 4 $ 番目のクエリでは、 $ 4 $ 列目に落ちているゴミはマス $ (3, 4) $ にあるゴミの $ 1 $ つであるため答えは $ 1 $ となります。このゴミは捨てられ、残ったゴミはマス $ (3, 1) $ に落ちているゴミです。 $ 5 $ 番目のクエリでは、 $ 2 $ 行目に落ちているゴミは存在しないため答えは $ 0 $ となります。 ### Constraints - $ 1 \leq H, W, N \leq 2 \times 10^5 $ - $ 1 \leq X_i \leq H $ - $ 1 \leq Y_i \leq W $ - $ i \neq j $ のとき $ (X_i, Y_i) \neq (X_j, Y_j) $ - $ 1 \leq Q \leq 2 \times 10^5 $ - タイプ $ 1 $ のクエリについて、 $ 1 \leq x \leq H $ - タイプ $ 2 $ のクエリについて、 $ 1 \leq y \leq W $ - 入力される値はすべて整数