AT_abc024_c [ABC024C] 民族大移動

[problemUrl]: https://atcoder.jp/contests/abc024/tasks/abc024_c 高橋王国には $ 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 $ 番目の民族が目的地に到着できる最初の日を出力せよ。 出力の末尾にも改行を入れること。

### Sample Explanation 1 $ 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 $ に移動する。