Công ty Đường sắt IOI vận hành một tuyến đường sắt thẳng có \(N\) ga, được đánh số từ \(1\) đến \(N\). Với mỗi \(1 \le i < N\), ga \(i\) và ga \(i+1\) được nối bằng đường ray.

Có \(M\) tuyến tàu được đánh số từ \(1\) đến \(M\). Tàu của tuyến \(j\) (\(1 \le j \le M\)) xuất phát tại ga \(A_j\), đi tới ga cuối \(B_j\) và dừng tại mọi ga trên đường đi:

• Nếu \(A_j < B_j\), tàu lần lượt dừng ở \(A_j,A_j+1,\ldots,B_j\).
• Nếu \(A_j > B_j\), tàu lần lượt dừng ở \(A_j,A_j-1,\ldots,B_j\).

JOI đang cân nhắc \(Q\) kế hoạch du lịch. Trong kế hoạch thứ \(k\) (\(1 \le k \le Q\)), cậu muốn đi từ ga \(S_k\) tới ga \(T_k\) bằng một số tuyến tàu.

Tuy nhiên, JOI đã mệt sau một hành trình dài và muốn lên một chuyến tàu vắng để có chỗ ngồi. Vì vậy, JOI chỉ lên tàu tại một trong \(K\) ga đầu tiên tính cả ga xuất phát, và không lên tàu tại ga cuối. Cụ thể:

• Nếu \(A_j < B_j\), cậu có thể lên tuyến \(j\) tại \(A_j,A_j+1,\ldots,\min(A_j+K-1,B_j-1)\).
• Nếu \(A_j > B_j\), cậu có thể lên tuyến \(j\) tại \(A_j,A_j-1,\ldots,\max(A_j-K+1,B_j+1)\).

Sau khi lên tàu, JOI có thể xuống tại bất kỳ ga nào từ ga kế tiếp theo hướng chạy đến ga cuối, kể cả ga cuối.

JOI muốn hạn chế việc đổi tàu. Với mỗi kế hoạch, hãy tìm số chuyến tàu ít nhất mà cậu phải lên để hoàn thành kế hoạch đó.

Dữ liệu vào

Dữ liệu được cho từ đầu vào chuẩn:

• Dòng đầu chứa \(N\) và \(K\).
• Dòng thứ hai chứa \(M\).
• \(M\) dòng tiếp theo, dòng thứ \(j\) chứa \(A_j\) và \(B_j\).
• Dòng tiếp theo chứa \(Q\).
• \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa \(S_k\) và \(T_k\).

Tất cả các giá trị đầu vào đều là số nguyên.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) chứa số chuyến tàu ít nhất mà JOI phải lên để hoàn thành kế hoạch thứ \(k\). Nếu không thể hoàn thành kế hoạch đó, in ra \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(1 \le K \le N-1\).
• \(1 \le M \le 200\,000\).
• \(1 \le A_j,B_j \le N\) và \(A_j \ne B_j\) với mọi \(1 \le j \le M\).
• \((A_j,B_j) \ne (A_k,B_k)\) với mọi \(1 \le j < k \le M\).
• \(1 \le Q \le 50\,000\).
• \(1 \le S_k,T_k \le N\) và \(S_k \ne T_k\) với mọi \(1 \le k \le Q\).
• \((S_k,T_k) \ne (S_l,T_l)\) với mọi \(1 \le k < l \le Q\).

Phân nhóm

• Nhóm 1 (8 điểm): \(N \le 300\), \(M \le 300\), \(Q \le 300\).
• Nhóm 2 (8 điểm): \(N \le 2000\), \(M \le 2000\), \(Q \le 2000\).
• Nhóm 3 (11 điểm): \(Q=1\).
• Nhóm 4 (25 điểm): \(K=N-1\).
• Nhóm 5 (35 điểm): \(A_j < B_j\) với mọi \(1 \le j \le M\), và \(S_k < T_k\) với mọi \(1 \le k \le Q\).
• Nhóm 6 (13 điểm): Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI 2021/2022, vòng chung kết, ngày 13/02/2022. Đề gốc của Ủy ban Olympic Tin học Nhật Bản: tiếng Nhật, tiếng Anh. Bản dịch theo giấy phép CC BY-SA 4.0.