AT_abc024_c [ABC024C] 民族大移動

### 题意简述 高桥君的王国有 $N$ 个城市，每个城市用编号 $1$ ~ $N$ 表示。 高桥国有 $K$ 个民族居住，第 $i$ 个民族生活在编号为 $S_i$ 的城市。 高桥国有百年一度的所有民族共同习俗**民族大迁徙**，但由于交通拥堵，所以设置了**第 $i$ 天只能在编号在 $L_i$ 到 $R_i$ 的城市来来去去**的限制，并最多花费 $D$ 天进行。 每个民族都遵守这一行动限制，在经过几个城市的同时前往目的地城市。 第 $i$ 个民族的目的地是 $T_i$ ，每个民族都希望尽可能早的到达目的地。 求每个民族最早到达目的地的时间。

第一行有 $3$ 个整数，分别为高桥国城市的个数 $N$ ，大迁徙的时间 $D$，高桥国所住的民族数 $K$。 接下来的 $D$ 行，有 $2$ 个整数 $L_i,R_i$，表示第 $i$ 天可来来去去的城市编号范围。 接下来的 $K$ 行，每行 $2$ 个整数 $S_i,T_i$，表示第 $i$ 个民族原本居住的城市编号和目的地城市编号。

共 $K$ 行，每行一个整数表示第 $i$ 个民族到达目的地的最少天数。 数据保证每个民族 $D$ 天内能到达目的地。

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