Cho \(N\) đoạn thẳng trên trục tọa độ, đoạn thẳng thứ \(i\) phủ từ tọa độ \(L_i\) đến \(R_i\) (\(0 \le L_i \le R_i \le 10^6\)).

Bạn cần xử lý \(Q\) truy vấn: Cho hai tọa độ \(A\) và \(B\) (\(0 \le A \le B \le 10^6\)), hãy tìm số lượng đoạn thẳng ít nhất cần chọn để phủ kín hoàn toàn khoảng tọa độ từ \(A\) đến \(B\). Nếu không thể phủ kín, in ra -1.

Một tập hợp các đoạn thẳng được gọi là phủ kín khoảng từ \(A\) đến \(B\) nếu hợp của chúng chứa toàn bộ đoạn \([A, B]\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L_i\) và \(R_i\) (\(0 \le L_i \le R_i \le 10^6\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) (\(0 \le A \le B \le 10^6\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra số lượng đoạn thẳng ít nhất cần dùng hoặc -1 nếu không thể phủ kín.

Ràng buộc & Subtasks

• Subtask 1 (35% số điểm): \(N, Q \le 1000\), các tọa độ không vượt quá \(1000\).
• Subtask 2 (65% số điểm): \(N, Q \le 10^5\), các tọa độ không vượt quá \(10^6\).

Ví dụ

Input:

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

Output:

2
2
2

Giải thích:

• Các đoạn thẳng cho trước: \([1, 3]\), \([2, 4]\), \([3, 6]\).
• Truy vấn 1 (\([1, 6]\)): Chọn \([1, 3]\) và \([3, 6]\) \(\to\) 2 đoạn.
• Truy vấn 2 (\([2, 5]\)): Chọn \([2, 4]\) và \([3, 6]\) \(\to\) 2 đoạn.
• Truy vấn 3 (\([1, 5]\)): Chọn \([1, 3]\) và \([3, 6]\) \(\to\) 2 đoạn.