原题链接

题目描述

有一个 $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$ 个查询的答案。

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

2
1
0
1
0

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

0
0
0
0
0
0
0

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

4
3
3
2
2
1
1

提示

「数据范围」

• $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$
• 输入的所有值均为整数

「样例解释 1」

开始时，垃圾掉落在单元格 $(1, 2), (1, 3), (3, 4), (3, 1), (2, 2)$ 上。

对于第 $1$ 个查询，第 $1$ 行掉落的垃圾是单元格 $(1, 2)$ 和 $(1, 3)$ 上的垃圾，共 $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$。