Cho một dãy gồm \(N\) phần tử đã được sắp xếp không giảm và \(Q\) truy vấn. Mỗi truy vấn gồm ba số \(l, r, val\) yêu cầu tìm số nhỏ nhất lớn hơn hoặc bằng \(val\) trong đoạn \(l\) đến \(r\). Bạn hãy trả lời các truy vấn đó nhé!

Dữ liệu

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\).

• Dòng tiếp theo gồm \(N\) số nguyên biểu diễn dãy.

• \(Q\) dòng tiếp theo, mỗi dòng gồm ba số nguyên \(l, r, val\) thể hiện một truy vấn.

Kết quả

• In ra \(Q\) dòng, mỗi dòng gồm một số nguyên để trả lời các truy vấn. Nếu không có kết quả thì in ra \(-1\).

Giới hạn

• 50% số điểm có \(1 ≤ N, Q ≤ 1000\).

• 50% số điểm còn lại có \(1 ≤ N, Q ≤ 10^5\).

• Các giá trị xuất hiện trong input có giá trị tuyệt đối không quá \(2∗10^9\).

Sample Input

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

Sample Output

2
1
4