Cho \(N\) đoạn thẳng trên trục số, đoạn thẳng thứ \(i\) giới hạn từ tọa độ \(L_i\) đến \(R_i\) (\(L_i \le R_i\)).

Bạn cần xử lý \(Q\) truy vấn: Mỗi truy vấn cho một đoạn \([A, B]\) (\(A \le B\)). Hãy tìm độ dài ngắn nhất của một đoạn thẳng trong tập cho trước giao với đoạn \([A, B]\). Độ dài của đoạn thẳng \([L_i, R_i]\) được tính bằng \(R_i - L_i\).

Nếu không có đoạn thẳng nào giao với \([A, B]\), in ra -1.

Đị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\) (\(-10^9 \le L_i \le R_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(A\) và \(B\) (\(-10^9 \le A \le B \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra độ dài ngắn nhất tìm được hoặc -1.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5\), các ràng buộc gốc.

Ví dụ

Input:

3 3
1 5
2 8
10 12
2 4
4 4
6 11

Output:

4
4
2

Giải thích:

• Các đoạn thẳng: \([1, 5]\) (độ dài 4), \([2, 8]\) (độ dài 6), \([10, 12]\) (độ dài 2).
• Truy vấn 1 (\([2, 4]\)): Giao với \([1, 5]\) và \([2, 8]\). Độ dài ngắn nhất là 4 (của đoạn \([1, 5]\)).
• Truy vấn 2 (\([4, 4]\)): Giao với \([1, 5]\) và \([2, 8]\). Độ dài ngắn nhất là 4.
• Truy vấn 3 (\([6, 11]\)): Giao với \([2, 8]\) và \([10, 12]\). Đoạn ngắn nhất là \([10, 12]\) có độ dài 2.