K-th Number

Source: POJ

Version: Phuoc Hung OJ Extended

Problem

The array contains $n$ distinct integers. Query $Q(i,j,k)$ asks for the $k$-th smallest value in $a_i..a_j$.

Input

The first line contains $n,m$, the second line contains $n$ distinct integers, and each of the next $m$ lines contains $i,j,k$.

Output

Print the $k$-th smallest value for each query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 1000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n\le10^5$
• $1\le m\le5000$
• $|a_i|\le10^9$ and all values are distinct
• $1\le i\le j\le n$
• $1\le k\le j-i+1$

Example

Input

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

Output

5
6
3

Explanation

The segment [5,2,6,3] becomes [2,3,5,6], so its third smallest value is $5$.