题目描述

高橋王国には, 東西にのびる $1$ 本の線路がある. これに沿って $N$ 個の都市があり, 西から順に都市 $1,\ 2,\ 3,\ \cdots,\ N$ と番号づけられている.
AtCoder Express という会社は $M$ 本の列車を保有しており, 列車 $i$ は都市 $L_i$ から都市 $R_i$ の区間 ($L_i\ =\ R_i$ の場合もある) を走っている.

この王国の国王である高橋君は, $Q$ 個のことに興味を持った. 具体的には, $i=1,\ 2,\ 3,\ \dots,\ Q$ のときの以下の質問の答えを求めたくなった.

• 都市 $p_i$ から都市 $q_i$ までの区間に, 走る区間が 完全に含まれる 列車の本数. 言い換えれば, $p_i\ \leq\ L_j$ と $R_j\ \leq\ q_i$ が両方成り立つような列車 $j$ の本数.

高橋君は天才である. しかし流石の彼でも, 膨大なデータを処理することはできない. 高橋君のために, $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$ までの区間に, それぞれの走る区間が完全に含まれる列車の本数を出力せよ.

题目大意

问有多少个给定的数对 $(i,j)$ 满足 $l\le i$ 且 $i\le r$。

2 3 1
1 1
1 2
2 2
1 2

3

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

1
1

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

7
9
10
6
8
9
6
7
8
10

提示

制約

• $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)$

Sample Explanation 1

全ての列車の走る区間が, 都市 $1$ から都市 $2$ までの区間に含まれているので, この質問の答えは $3$ となる.

Sample Explanation 2

$1$ 個目の質問は, 都市 $1$ から $7$ までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 $1$ のみである. $2$ 個目の質問は, 都市 $3$ から $10$ までの区間についてである. その区間に走る区間が完全に含まれている列車は, 列車 $3$ のみである.