Problem Description

The IOI Railway Company operates routes on a single railway track. The track is a straight line, and there are $N$ stations on it, numbered $1 \sim N$. Station $i$ and station $i + 1$ are directly connected by a piece of track.

The IOI Railway Company is operating $M$ routes, numbered $1 \sim M$. Route $j$ starts at $A_j$ and ends at $B_j$, and the train stops at every station. That is, if $A_j < B_j$, a train on route $j$ stops in order at stations $A_j, A_j + 1, \ldots, B_j$. If $A_j > B_j$, a train on route $j$ stops in order at stations $A_j, A_j - 1, \ldots, B_j$.

JOI is a traveler. He has $Q$ travel plans. In the $k$-th travel plan, he plans to travel from station $S_k$ to station $T_k$ by taking trains.

However, JOI is exhausted from long-distance travel. He wants every train he takes to have an empty seat so that he can rest. Therefore, JOI will only board within $K$ stations from the starting station of a route (including the starting station). In other words, for route $j$, if $A_j < B_j$, then he will only board a train on route $j$ at stations $A_j, A_j + 1, \ldots, \min \{ A_j + K - 1, B_j - 1 \}$. If $A_j > B_j$, then he will only board a train on route $j$ at stations $A_j, A_j - 1, \ldots, \max \{ A_j - K + 1, B_j + 1 \}$.

Under these conditions, JOI wants to minimize the number of train rides as much as possible.

Given the route information of the IOI Railway Company and JOI's plans, write a program to compute, for each of JOI's plans, the minimum number of rides he needs.

Input Format

The first line contains two positive integers $N, K$.

The second line contains one positive integer $M$.

The next $M$ lines each contain two positive integers $A_j, B_j$ on the $j$-th line.

The next line contains one positive integer $Q$.

The next $Q$ lines each contain two positive integers $S_k, T_k$ on the $k$-th line.

Output Format

Output $Q$ lines. The $k$-th line contains one number, representing the minimum number of rides needed for JOI to complete his $k$-th plan. If it is impossible to complete the $k$-th plan, output -1.

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

1
2
-1

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

1
-1
1
2

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

-1
1
2
-1
1

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

-1
1
4
-1
2
-1
1

Hint

[Sample Explanation #1]

For the first plan, JOI wants to travel from station $5$ to station $3$. Specifically, this plan can be carried out as follows: JOI boards route $1$ at station $5$ and gets off at station $3$. In total, JOI takes one train. Since it is impossible to complete this plan with fewer than $1$ ride, output $1$ on the first line.

For the second plan, JOI wants to travel from station $3$ to station $2$. Specifically, this plan can be carried out as follows: JOI boards route $2$ at station $3$ and gets off at station $4$; then he boards route $1$ at station $4$ and gets off at station $2$. In total, JOI takes two trains. Since it is impossible to complete this plan with fewer than $2$ rides, output $2$ on the second line.

For the third plan, JOI wants to travel from station $2$ to station $1$. Since it is impossible to complete this plan, output -1 on the third line.

This sample satisfies the constraints of subtasks $1, 2, 6$.

[Sample Explanation #2]

This sample satisfies the constraints of subtasks $1, 2, 6$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 2, 4, 6$.

[Sample Explanation #4]

This sample satisfies the constraints of subtasks $1, 2, 5, 6$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata, $2 \le N \le {10}^5$, $1 \le K \le N - 1$, $1 \le M \le 2 \times {10}^5$, $1 \le Q \le 5 \times {10}^4$, $1 \le A_j, B_j, S_k, T_k \le N$, $A_j \ne B_j$, $S_k \ne T_k$, $(A_j, B_j) \ne (A_k, B_k)$ ($j \ne k$), $(S_k, T_k) \ne (S_l, T_l)$ ($k \ne l$).

• Subtask $1$ ($8$ points): $N, M, Q \le 300$.
• Subtask $2$ ($8$ points): $N, M, Q \le 2000$.
• Subtask $3$ ($11$ points): $Q = 1$.
• Subtask $4$ ($25$ points): $K = N - 1$.
• Subtask $5$ ($35$ points): $A_j < B_j$, $S_k < T_k$.
• Subtask $6$ ($13$ points): No special constraints.

Translated from JOI 2022 Final T4 "鉄道旅行 2 / Railway Trip 2".

Translated by ChatGPT 5