問題文

高橋王国には $N$ 個の街があり、それぞれ $1$ ～ $N$ の整数によって番号付けされています。

高橋王国には $K$ 種類の民族が住んでおり、$i$ 番目の民族は街 $S_i$ に住んでいます。

高橋王国の民族たちには、百年に一回住む街を変える「民族大移動」という文化が有ります。 基本的には全民族が同時期に「民族大移動」を行うのですが、全く同じ日に全民族が移動すると混雑が予想されるため、 以下の様な移動制限を毎日設けて、 $D$ 日かけて行います。

• $i$ 日目は 街の番号が $L_i$ 以上 $R_i$ 以下であるよう街の間を自由に行き来できる。それ以外の行き来は禁止される。

各民族はこの移動制限を守り、いくつかの街を経由しながら目的地の街まで移動します。

$i$ 番目の民族の目的地は街 $T_i$ です。どの民族もできるだけ早く目的地に到着したいと思っています。

各民族について、目的地に到着できる最も早い日を求めてください。

なお、どの民族も $D$ 日以内に目的地に到着できることが保証されています。

---

入力

入力は以下の形式で標準入力から与えられる。

$N$ $D$ $K$ $L_1$ $R_1$ $L_2$ $R_2$ : $L_D$ $R_D$ $S_1$ $T_1$ $S_2$ $T_2$ : $S_K$ $T_K$

• $1$ 行目には高橋王国の街の個数 $N(1 ≦ N ≦ 10^9)$ 、大移動にかける日数 $D(1 ≦ D ≦ 10^4)$ 、高橋王国に住む民族の個数 $K(1 ≦ K ≦ 100)$ が空白区切りで与えられる。
• $2$ 行目からの $D$ 行のうち $i$ 行目には $i$ 日目の移動制限の内容を表す $2$ つの整数 $L_i, R_i(1 ≦ L_i ≦ R_i ≦ N)$ が空白区切りで与えられる。
• $D+2$ 行目からの $K$ 行のうち $i$ 行目には $i$ 番目の民族の初め住んでいる街 $S_i( 1 ≦ S_i ≦ N)$、目的地の街 $T_i (1 ≦ T_i ≦ N)$ が空白区切りで与えられる。このとき $S_i ≠ T_i$ が成り立つ。
• どの民族も $D$ 日以内に目的地に到着できることが保証されている。

出力

出力は $K$ 行からなる。 $i$ 行目には $i$ 番目の民族が目的地に到着できる最初の日を出力せよ。 出力の末尾にも改行を入れること。

---

入力例1

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

出力例1

2
4
8

$1$ 番目の民族は以下のように移動すれば $2$ 日で目的地に到着できます。これより早く移動することはできません。

• $1$ 日目に街 $1$ から街 $4$ に移動する。
• $2$ 日目に街 $4$ から街 $6$ に移動する。

$2$ 番目の民族は以下のように移動すれば $4$ 日で目的地に到着できます。これより早く移動することはできません。

• $1$ 日目に街 $2$ から街 $5$ に移動する。
• $4$ 日目に街 $5$ から街 $7$ に移動する。

$3$ 番目の民族は以下のように移動すれば $8$ 日で目的地に到着できます。これより早く移動することはできません。

• $3$ 日目に街 $10$ から街 $9$ に移動する。
• $7$ 日目に街 $9$ から街 $3$ に移動する。
• $8$ 日目に街 $3$ から街 $1$ に移動する。

---

入力例2

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

出力例2

10
4
2
2

---

入力例3

314159265 10 1
1 10000
500 12031
1414 113232
111111 777777
666661 23423423
12345678 123456789
111111111 314159265
112334 235235235
1 223445
314 1592
1 314159265

出力例3

7

---