Cho mảng \(A\) gồm N phần tử. Bạn cần thực hiện Q truy vấn: với mỗi truy vấn, tìm phần tử có giá trị nhỏ nhất nhưng vẫn lớn hơn X nằm trong đoạn con từ vị trí L đến \(R\) (1-indexed).

Nếu không có phần tử nào trong đoạn \([L, R]\) có giá trị lớn hơn \(X\), 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\)).
• Dòng hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) (\(-10^9 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa ba số nguyên L, R và X (\(1 \le L \le R \le N, -10^9 \le X \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị nhỏ nhất tìm được hoặc -1 nếu không tồn tại.

Ví dụ

Input:

5 3
4 2 7 1 5
1 3 3
2 5 5
1 5 10

Output:

4
7
-1

Giải thích:

• Truy vấn 1: Đoạn \([1..3]\) là \([4, 2, 7]\). Các giá trị > 3$ là \(\{4, 7\}\), nhỏ nhất là 4.
• Truy vấn 2: Đoạn \([2..5]\) là \([2, 7, 1, 5]\). Các giá trị > 5$ chỉ có \(\{7\}\), nhỏ nhất là 7.
• Truy vấn 3: Toàn mảng không có phần tử nào \(> 10 \to\) -1.

Ràng buộc & Subtasks

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