问题描述

高桥王国有 $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$

• 第一行包含高桥王国的城市数量 $N(1 ≦ N ≦ 10^9)$、完成大迁徙所需天数 $D(1 ≦ D ≦ 10^4)$，以及居住在高桥王国的种族数量 $K(1 ≦ K ≦ 100)$。
• 从第二行开始的 $D$ 行中，第 $i$ 行包含表示第 $i$ 天移动限制的两个整数 $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

第一个种族按以下方式移动，将在第 $2$ 天到达目的地。不能更早地移动。

• 第 $1$ 天从城市 $1$ 移动到城市 $4$。
• 第 $2$ 天从城市 $4$ 移动到城市 $6$。

第二个种族按以下方式移动，将在第 $4$ 天到达目的地。不能更早地移动。

• 第 $1$ 天从城市 $2$ 移动到城市 $5$。
• 第 $4$ 天从城市 $5$ 移动到城市 $7$。

第三个种族按以下方式移动，将在第 $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