Problem Description

IOI Railway operates a single railway line. The IOI railway line has $ N $ stations numbered from $ 1 $ to $ N $ arranged in a straight line. For each $ i $ ($1 \leq i \leq N - 1$), station $ i $ and station $ i + 1 $ are connected by a railway.

The IOI railway line has $ M $ train lines numbered from $ 1 $ to $ M $. The starting station of the train on line $ j $ ($1 \leq j \leq M$) is station $ A_j $, and the terminal station is station $ B_j $. Trains stop at every station. That is, the train on line $ j $ stops at stations $A_j, A_j + 1, \dots, B_j$ if $ A_j < B_j $, and at stations $A_j, A_j - 1, \dots, B_j$ if $ A_j > B_j $.

Traveler JOI is planning $ Q $ trips. The $ k $-th ($1 \leq k \leq Q$) plan is to depart from station $ S_k $ and arrive at station $ T_k $ by transferring between trains.

However, JOI is tired from long journeys and wants to board trains that are not crowded and can sit down. Therefore, JOI will only board a train from a station within $ K $ stations from the starting station (including the starting station itself). That is, when JOI boards a train on line $ j $, if $ A_j < B_j $, they can board from stations $A_j, A_j + 1, \dots, \min\{A_j + K - 1, B_j - 1\}$, and if $ A_j > B_j $, they can board from stations $A_j, A_j - 1, \dots, \max\{A_j - K + 1, B_j + 1\}$. JOI will get off the train at any station from the next station they boarded to the terminal station.

JOI wants to minimize the number of train transfers under these conditions.

Given the information about the IOI railway line and JOI's plans, create a program that calculates the minimum number of trains JOI needs to board for each plan.

Input Format

The input is given from the standard input in the following format. All values are integers.

$ 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 $

Output Format

Output $ Q $ lines to the standard output. The $ k $-th line ($1 \leq k \leq Q$) should contain the minimum number of trains JOI needs to board to achieve the $ k $-th plan. If the plan is impossible to achieve, output -1.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
-1

Sample Input #2

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

Sample Output #2

1
-1
1
2

Sample Input #3

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

Sample Output #3

-1
1
2
-1
1

Sample Input #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

Sample Output #4

-1
1
4
-1
2
-1
1

Notes/Hints

Constraints

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

Subtasks

1. ($ 8 $ points) $N \leq 300$, $M \leq 300$, $Q \leq 300$.
2. ($ 8 $ points) $N \leq 2,000$, $M \leq 2,000$, $Q \leq 2,000$.
3. ($ 11 $ points) $ Q = 1 $.
4. ($ 25 $ points) $ K = N - 1 $.
5. ($ 35 $ points) $ A_j < B_j $ ($1 \leq j \leq M$), $ S_k < T_k $ ($1 \leq k \leq Q$).
6. ($ 13 $ points) No additional constraints.

Sample Explanation 1

The first plan is to depart from station $ 5 $ and arrive at station $ 3 $. For example, by boarding the train on line $ 1 $ at station $ 5 $ and getting off at station $ 3 $, the plan can be achieved. The number of trains boarded is $ 1 $. It is impossible to achieve the plan with fewer than $ 1 $ train, so output $ 1 $ on the first line. The second plan is to depart from station $ 3 $ and arrive at station $ 2 $. For example, by boarding the train on line $ 2 $ at station $ 3 $, getting off at station $ 4 $, and then boarding the train on line $ 1 $ at station $ 4 $ and getting off at station $ 2 $, the plan can be achieved. The number of trains boarded is $ 2 $. It is impossible to achieve the plan with fewer than $ 2 $ trains, so output $ 2 $ on the second line. Note that it is not possible to board the train on line $ 1 $ from station $ 3 $. The third plan is to depart from station $ 2 $ and arrive at station $ 1 $. This plan is impossible to achieve, so output -1 on the third line. This input example satisfies the constraints of subtasks $ 1, 2, 6 $.

Sample Explanation 2

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

Sample Explanation 3

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

Sample Explanation 4

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

见题面 Input 部分

见题面 Output 部分