Given an array ~A~ of ~N~ numbers, you need to answer ~Q~ queries of the form l' r' k', where you output the ~k^\text{th}~ minimum number in the range ~[l, r]~.

Constraints

~1 \le N, Q \le 200\,000~

~1 \le l \le r \le N~

~1 \le k \le r-l+1~

~1 \le A_i \le 10^9~

Input Specification

The first line will contain ~N~ and ~Q~, the number of elements in the array and the number of queries.

The second line will contain ~N~ space-separated integers, the elements of ~A~.

The next ~Q~ lines will contain a query defined above.

Note that this problem will be online enforced, meaning that input will be given in an encrypted format. To encrypt the data, the values ~l, r, k~ in queries will be given as ~l' = l \oplus \text{lastAns}, r' = r \oplus \text{lastAns}~, and ~k' = k \oplus \text{lastAns}~, where ~\oplus~ denotes the bitwise XOR operation. Note that ~\text{lastAns}~ at any time is defined as the answer to the latest query. If no queries have occurred so far, ~\text{lastAns} = 0~.

Output Specification

Output ~Q~ lines, the answers to the queries.

Sample Input (Encrypted)

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

Sample Input (Unencrypted)

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

Sample Output

3
5
4
3
5