Range Lower Bound Query

Problem Description

You are given $n$ numbers $a_1, a_2, \dots, a_n$ and $q$ queries:

• l r x: among $a_l, a_{l+1}, \dots, a_r$, find the smallest number that is greater than or equal to $x$.

Input Format

The first line contains two integers $n, q\ (1 \le n, q \le 2 \times 10^5)$.

The next line contains $n$ integers $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)$.

The next $q$ lines each contain three integers $l, r, x\ (1 \le l \le r \le n,\ 1 \le x \le 10^9)$.

Output Format

For each query, output one number: the answer. If no such number exists, output -1.

Sample Input

5 5
2 4 1 5 3
1 5 6
1 4 3
3 4 3
2 4 2
3 3 1

Sample Output

-1
4
5
4
1