题目描述

给定一个 $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$ —— 分别表示网格的行数、列数和垃圾的数量。

接下来 $N$ 行，每行包含两个正整数 $X_i$ 和 $Y_i$ —— 表示第 $i$ 个垃圾的坐标。

第 $N+2$ 行包含一个正整数 $Q$ —— 表示查询的数量。

接下来 $Q$ 行，每行描述一个查询，格式为 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

样例输入 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

说明

样例解释

在第一个样例中，初始时垃圾分别位于格子 $(1,2), (1,3), (3,4), (3,1), (2,2)$。

• 在第 $1$ 个查询中，第 $1$ 行有 $2$ 个垃圾，分别位于 $(1,2)$ 和 $(1,3)$，因此输出 $2$。接着这些垃圾被清除；剩下的垃圾位于 $(3,4), (3,1), (2,2)$。
• 在第 $2$ 个查询中，第 $2$ 行有 $1$ 个垃圾，位于 $(2,2)$，因此输出 $1$。接着该垃圾被清除；剩下的垃圾位于 $(3,4), (3,1)$。
• 在第 $3$ 个查询中，第 $2$ 列没有任何垃圾，因此输出 $0$。
• 在第 $4$ 个查询中，第 $4$ 列有 $1$ 个垃圾，位于 $(3,4)$，因此输出 $1$。接着该垃圾被清除；剩下的垃圾位于 $(3,1)$。
• 在第 $5$ 个查询中，第 $2$ 行没有任何垃圾，因此输出 $0$。

数据范围

• 对于所有测试点，保证 $1 \le H, W, N \le 2 \times 10^5$。
• 保证 $1 \le X_i \le H$ 且 $1 \le Y_i \le W$。
• 保证所有的垃圾位置互不相同，即对于 $i \neq j$，有 $(X_i, Y_i) \neq (X_j, Y_j)$。
• 对于所有测试点，保证 $1 \le Q \le 2 \times 10^5$。
• 对于类型 $1$ 的查询，保证 $1 \le x \le H$。
• 对于类型 $2$ 的查询，保证 $1 \le y \le W$。
• 保证所有的输入数值均为整数。