IOI 铁路公司在一条铁轨上运营线路。铁轨上有 $N$ 个车站，排成一条直线，编号从 $1$ 到 $N$。对于每个 $i$ ($1 \le i \le N - 1$)，车站 $i$ 和车站 $i + 1$ 由一段铁轨直接相连。

IOI 铁路公司运营着 $M$ 条线路，编号从 $1$ 到 $M$。对于线路 $j$ ($1 \le j \le M$)，起始站为车站 $A_j$，终点站为车站 $B_j$。列车在每一站都会停靠。具体来说，如果 $A_j < B_j$，线路 $j$ 的列车依次停靠在车站 $A_j, A_j + 1, \dots, B_j$。如果 $A_j > B_j$，线路 $j$ 的列车依次停靠在车站 $A_j, A_j - 1, \dots, B_j$。

JOI-kun 是一位旅行者。他有 $Q$ 个旅行计划。在第 $k$ 个计划 ($1 \le k \le Q$) 中，他要从车站 $S_k$ 前往车站 $T_k$。

然而，JOI-kun 长途跋涉后感到疲惫。他想乘坐空车并获得座位。因此，JOI-kun 决定只有在车站是该线路从起点出发的第 $K$ 站或更早的车站时，他才会上车。换句话说，如果 $A_j < B_j$，他只能在车站 $A_j, A_j + 1, \dots, \min\{A_j + K - 1, B_j - 1\}$ 上车。如果 $A_j > B_j$，他只能在车站 $A_j, A_j - 1, \dots, \max\{A_j - K + 1, B_j + 1\}$ 上车。JOI-kun 将在从他上车站点的下一站到终点站之间的任意车站（包含两端）下车。

在这些条件下，JOI-kun 希望最小化乘坐列车的次数。

给定 IOI 铁路公司的线路信息和 JOI-kun 的旅行计划，请编写一个程序，计算对于 JOI-kun 的每个计划，他实现该计划所需的最少乘车次数。

输入格式

从标准输入读取以下数据。所有给定的值均为整数。

$N \ K$ $M$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$ $Q$ $S_1 \ T_1$ $S_2 \ T_2$ $\vdots$ $S_Q \ T_Q$

输出格式

输出 $Q$ 行到标准输出。第 $k$ 行 ($1 \le k \le Q$) 应包含 JOI-kun 实现第 $k$ 个计划所需的最少乘车次数。如果无法实现第 $k$ 个计划，则输出 $-1$。

数据范围

• $2 \le N \le 100\,000$。
• $1 \le K \le N - 1$。
• $1 \le M \le 200\,000$。
• $1 \le A_j \le N$ ($1 \le j \le M$)。
• $1 \le B_j \le N$ ($1 \le j \le M$)。
• $A_j \neq B_j$ ($1 \le j \le M$)。
• $(A_j, B_j) \neq (A_k, B_k)$ ($1 \le j < k \le M$)。
• $1 \le Q \le 50\,000$。
• $1 \le S_k \le N$ ($1 \le k \le Q$)。
• $1 \le T_k \le N$ ($1 \le k \le Q$)。
• $S_k \neq T_k$ ($1 \le k \le Q$)。
• $(S_k, T_k) \neq (S_l, T_l)$ ($1 \le k < l \le Q$)。

子任务

1. (8 分) $N \le 300, M \le 300, Q \le 300$。
2. (8 分) $N \le 2\,000, M \le 2\,000, Q \le 2\,000$。
3. (11 分) $Q = 1$。
4. (25 分) $K = N - 1$。
5. (35 分) $A_j < B_j$ ($1 \le j \le M$), $S_k < T_k$ ($1 \le k \le Q$)。
6. (13 分) 无附加限制。

样例

样例输入 1

5 2
2
5 1
3 5
3
5 3
3 2
2 1

样例输出 1

1
2
-1

样例输入 2

6 3
2
1 6
5 1
4
5 1
6 3
3 6
2 1

样例输出 2

1
-1
1
2

样例输入 3

6 5
4
3 1
2 4
5 3
4 6
5
1 5
3 2
2 6
6 3
5 4

样例输出 3

-1
1
2
-1
1

样例输入 4

12 1
5
1 7
10 12
3 5
8 10
5 9
7
2 11
5 8
3 12
4 6
1 9
9 10
1 4

样例输出 4

-1
1
4
-1
2
-1
1