题目描述

暑假共有 $N$ 天，依次编号为 $1$ 到 $N$。期间计划举办 $M$ 个活动。

第 $i$ 个活动从第 $A_i$ 天早晨开始，到第 $B_i$ 天晚上结束。参加一个活动时，必须从活动开始一直参加到活动结束，不能只参加其中一部分。

你不能同时参加时间有重叠的两个活动。

请回答 $Q$ 个询问。每个询问给出两个整数 $L,R$，要求在第 $L$ 天至第 $R$ 天之间完整参加若干活动，并使参加的活动数量最大。也就是说，所选活动必须满足

且任意两个所选活动的举办时间不重叠。

限制条件

• $1\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $1\le Q\le 2\times 10^5$
• $1\le A_i\le B_i\le N$
• $1\le L\le R\le N$
• 所有输入均为整数。

输入

N M Q
A_1 B_1
A_2 B_2
...
A_M B_M
L_1 R_1
L_2 R_2
...
L_Q R_Q

输出

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

样例输入 1

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

样例输出 1

2
0
1

对于第一个询问，可以参加第 $1$ 个和第 $2$ 个活动，共参加 $2$ 个活动。

样例输入 2

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

样例输出 2

1
1
1
0
2
1
0
1