题目描述

在高桥王国中，有一条东西向的铁路，沿着它有 $N$ 个城市，从西到东依次编号为 $1$，$2$，$3$，...，$N$。一家名为 AtCoder Express 的公司拥有 $M$ 列火车，第 $i$ 列火车从城市 $L_i$ 开往城市 $R_i$（可能存在 $L_i = R_i$）。高桥王对以下 $Q$ 个问题感兴趣：

• 在从城市 $p_i$ 到城市 $q_i$ 的区间内严格运行的火车数量，即满足 $p_i \\leq L_j$ 且 $R_j \\leq q_i$ 条件的火车数量 $j$。

尽管他是个天才，但这些数据量太大了，他无法独自处理。找出每个问题的答案以帮助他。

约束条件

• $N$ 是一个介于 $1$ 和 $500$（含端点）之间的整数。
• $M$ 是一个介于 $1$ 和 $200 \\ 000$（含端点）之间的整数。
• $Q$ 是一个介于 $1$ 和 $100 \\ 000$（含端点）之间的整数。
• $1 \\leq L_i \\leq R_i \\leq N$ $(1 \\leq i \\leq M)$
• $1 \\leq p_i \\leq q_i \\leq N$ $(1 \\leq i \\leq Q)$

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $Q$ $L_1$ $R_1$ $L_2$ $R_2$ $:$ $L_M$ $R_M$ $p_1$ $q_1$ $p_2$ $q_2$ $:$ $p_Q$ $q_Q$

输出

输出应包含 $Q$ 行。第 $i$ 行应包含从城市 $p_i$ 到城市 $q_i$ 的区间内严格运行的火车数量。

示例输入 1

2 3 1
1 1
1 2
2 2
1 2

示例输出 1

3

由于所有火车都在从城市 $1$ 到城市 $2$ 的区间内运行，所以唯一查询的答案是 $3$。

示例输入 2

10 3 2
1 5
2 8
7 10
1 7
3 10

示例输出 2

1
1

第一个查询是在从城市 $1$ 到 $7$ 的区间内。只有一列在该区间内运行的火车：火车 $1$。第二个查询是在从城市 $3$ 到 $10$ 的区间内。只有一列在该区间内运行的火车：火车 $3$。

示例输入 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

示例输出 3

7
9
10
6
8
9
6
7
8
10