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 đoạn thẳng giao với \([A, B]\) có tọa độ đầu mút phải (\(R_i\)) lớn nhất.

Nếu có nhiều đoạn thẳng có cùng tọa độ đầu mút phải lớn nhất, chọn đoạn thẳng có hoành độ đầu mút trái (\(L_i\)) nhỏ nhất. 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 tọa độ đầu mút trái và đầu mút phải của đoạn thẳng tìm được cách nhau bởi dấu cách. Nếu không tồn tại, in ra -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 3
2 8
10 12
2 4
4 4
6 7

Output:

2 8
-1
2 8

Giải thích:

• Đoạn thẳng: \([1, 3]\), \([2, 8]\), \([10, 12]\).
• Truy vấn 1 (\([2, 4]\)): Giao với \([1, 3]\) và \([2, 8]\). Đoạn có mút phải lớn nhất là \([2, 8]\).
• Truy vấn 2 (\([4, 4]\)): Không giao đoạn nào \(\to\) -1.
• Truy vấn 3 (\([6, 7]\)): Giao với \([2, 8]\) \(\to\) \([2, 8]\).