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.

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.

Ràng buộc & Subtasks

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