Problem Statement

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

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

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

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

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

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

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

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

Input

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

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$ 日以内に目的地に到着できることが保証されている。

Output

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