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 200000$

$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^{\prime }=l\oplus \text{lastAns},r^{\prime }=r\oplus \text{lastAns}$, and $k^{\prime }=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