D - Garbage Removal Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

H 行 W 列のマス目があり、上から i 行目、左から j 列目のマスをマス (i, j) と表記します。

マス目の上には N 個のゴミが落ちており、i 番目のゴミはマス (X_i, Y_i) に落ちています。

Q 個のクエリが与えられるので、順に処理したときの各クエリの答えを求めてください。各クエリは、以下のいずれかです。

  • タイプ 1 : 1 x の形式で入力として与えられる。マス目の x 行目に落ちているゴミの個数を答えとして求める。その後、x 行目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。

  • タイプ 2 : 2 y の形式で入力として与えられる。マス目の y 列目に落ちているゴミの個数を答えとして求める。その後、y 列目に落ちているゴミはすべて捨てられ、マス目上から取り除かれる。

制約

  • 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
  • 入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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 番目のクエリの答えを出力せよ。

入力例 1

3 4 5
1 2
1 3
3 4
3 1
2 2
5
1 1
1 2
2 2
2 4
1 2

出力例 1

2
1
0
1
0

はじめ、ゴミはマス (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 となります。

入力例 2

1 2 1
1 2
7
2 1
2 1
2 1
2 1
2 1
2 1
2 1

出力例 2

0
0
0
0
0
0
0

入力例 3

4 4 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
7
2 1
1 1
2 2
1 2
2 3
1 3
2 4

出力例 3

4
3
3
2
2
1
1

Score : 400 points

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

There are N pieces of trash on the grid; the i-th piece is at cell (X_i, Y_i).

You are given Q queries, which you must process in order. Each query is of one of the following types:

  • Type 1: Given in the format 1 x in the input. Report the number of trash pieces in the x-th row. Then, all trash pieces in the x-th row are removed from the grid.

  • Type 2: Given in the format 2 y in the input. Report the number of trash pieces in the y-th column. Then, all trash pieces in the y-th column are removed from the grid.

Constraints

  • 1 \leq H, W, N \leq 2 \times 10^5
  • 1 \leq X_i \leq H
  • 1 \leq Y_i \leq W
  • If i \neq j, then (X_i, Y_i) \neq (X_j, Y_j).
  • 1 \leq Q \leq 2 \times 10^5
  • For a type 1 query, 1 \leq x \leq H.
  • For a type 2 query, 1 \leq y \leq W.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Here, \text{query}_i denotes the i-th query, which is given in one of the following formats:

1 x

2 y

Output

Output Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

3 4 5
1 2
1 3
3 4
3 1
2 2
5
1 1
1 2
2 2
2 4
1 2

Sample Output 1

2
1
0
1
0

Initially, trash pieces are at cells (1, 2), (1, 3), (3, 4), (3, 1), (2, 2).

In the 1st query, the 1st row contains two pieces of trash at (1, 2) and (1, 3), so report 2. These pieces are then removed; the remaining trash is at (3, 4), (3, 1), (2, 2).

In the 2nd query, the 2nd row contains one piece of trash at (2, 2), so report 1. This piece is then removed; the remaining trash is at (3, 4), (3, 1).

In the 3rd query, the 2nd column contains no trash, so report 0.

In the 4th query, the 4th column contains one piece of trash at (3, 4), so report 1. This piece is then removed; the remaining trash is at (3, 1).

In the 5th query, the 2nd row contains no trash, so report 0.

Sample Input 2

1 2 1
1 2
7
2 1
2 1
2 1
2 1
2 1
2 1
2 1

Sample Output 2

0
0
0
0
0
0
0

Sample Input 3

4 4 16
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
7
2 1
1 1
2 2
1 2
2 3
1 3
2 4

Sample Output 3

4
3
3
2
2
1
1