乐队计数

题目描述

有一个 $H$ 行 $W$ 列的网格。用 $(i,j)$ 表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子。

网格上放置了 $N$ 个棋子，第 $i$ 个棋子位于 $(R_i,C_i)$。

请回答 $Q$ 个询问。每个询问是以下两种类型之一：

• 1 u d：输出位于第 $u$ 行到第 $d$ 行中的所有棋子数量；
• 2 l r：输出位于第 $l$ 列到第 $r$ 列中的所有棋子数量。

输入格式

输入第一行为四个整数 $H,W,N,Q$。

接下来 $N$ 行，第 $i$ 行为两个整数 $R_i,C_i$。

接下来 $Q$ 行，每行描述一个询问，格式为 1 u d 或 2 l r。

输出格式

输出 $Q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。

5 7 5 6
1 1
2 3
2 5
4 3
5 7
1 2 4
2 3 5
1 3 3
2 1 7
1 2 2
2 7 7

3
3
0
5
2
1

样例 1 解释

第 $1$ 个询问中，位于第 $2$ 行到第 $4$ 行的棋子是第 $2,3,4$ 个，共 $3$ 个。

17 23 12 12
14 8
2 19
17 3
7 11
2 4
10 19
7 8
1 23
14 11
2 23
17 19
7 2
1 2 7
2 9 20
1 3 6
2 8 8
1 11 17
2 1 23
1 1 1
2 20 22
1 7 14
2 3 11
1 15 17
2 19 23

6
5
0
2
4
12
1
0
6
6
2
5

数据范围

对于所有测试数据，保证：

• $1 \le H,W \le 10^9$；
• $1 \le N \le \min(H \times W, 3 \times 10^5)$；
• $1 \le R_i \le H$，$1 \le C_i \le W$；
• 当 $i \neq j$ 时，$(R_i,C_i) \neq (R_j,C_j)$；
• $1 \le Q \le 3 \times 10^5$；
• $1 \le u \le d \le H$，$1 \le l \le r \le W$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。