有一个国家，其环形公路呈圆形。环形公路上有 $L$ 座城市，它们均匀分布，相邻城市间的距离为 $1$。环形公路上的相邻城市之间由弧形道路连接。不幸的是，贪婪的 Batyr I 国王将这些道路设为收费道路，每经过一段路程需支付 $1$ 枚金币。但 Tima the Great 修建了 $m$ 条非法道路，这些道路以直线（弦）连接两座城市，第 $i$ 条道路连接编号为 $a_i$ 和 $b_i$ 的两座城市。
居民现在可以同时使用收费道路和免费道路。在旅行过程中，居民可以在 Tima 修建的道路的交点处随意改变方向，且这些操作是免费的！
给定 $q$ 次询问，对于第 $i$ 次询问，请确定居民从城市 $x_i$ 到城市 $y_i$ 旅行所需花费的最少金币数量。
输入格式
第一行包含三个整数 $L, m, q$ ($1 \le L \le 10^9, 0 \le m \le 10^5, 1 \le q \le 10^5$)，分别表示该国的城市数量、Tima the Great 修建的非法道路数量以及询问次数。
接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i < b_i \le L$)，表示第 $i$ 条非法道路连接的两座城市。
接下来的 $q$ 行，每行包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le L$)，表示居民需要旅行的起点城市和终点城市。
输出格式
输出 $q$ 行，第 $i$ 行输出从城市 $x_i$ 到城市 $y_i$ 旅行所需支付的最少金币数量。
子任务
| 子任务 | 附加约束 | 分值 | ||
|---|---|---|---|---|
| 0 | 样例 | 0 | ||
| 1 | $m = 0$ | 5 | ||
| 2 | $L, m, q \le 10^2$ | 8 | ||
| 3 | $L, m, q \le 10^3$ | 11 | ||
| 4 | $m, q \le 10^3$ | 10 | ||
| 5 | $b_i < a_{i+1}$ | 12 | ||
| 6 | $a_i < a_{i+1}, b_{i+1} < b_i$ | 14 | ||
| 7 | $ | x_i - y_i | = 1$ ($1 \le i \le q$) | 18 |
| 8 | 无附加约束 | 22 |
样例
输入 1
12 3 5 1 11 6 9 2 7 11 5 10 3 9 11 4 5 2 9
输出 1
2 2 1 1 0
说明
图中用箭头展示了从城市 11 到城市 5 的路径。