配点: $400$ 点

問題文

高橋王国には, 東西にのびる $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$ は $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$ までの区間に, それぞれの走る区間が完全に含まれる列車の本数を出力せよ.

2 3 1
1 1
1 2
2 2
1 2

3

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

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

1
1

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

7
9
10
6
8
9
6
7
8
10