时间限制：1秒　　内存限制：256M

---

【题目描述】

　　野生动物园从西到东被划分成 \(N\) 个区域，每个区域都饲养着一头狮子。这些狮子从西到东编号为 \(1,2,3,…,N\)。每头狮子都有一个觅食能力值 \(A[i]\)，其值越小觅食能力越强。

　　小H决定对狮子进行 \(M\) 次投喂，每次投喂都选择一个区间 \([i,j]\)，从中选取觅食能力值第 \(k\) 强（这里的第 \(k\) 强是指把 \(A[i]...A[j]\) 由小到大排序后的第 \(k\) 个）的狮子进行投喂。值得注意的是，小H不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此小H的 投喂区间是互不包含 的。

　　你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

【输入格式】

　　输入第一行有两个数 \(N\) 和 \(M\)，此后一行有 \(N\) 个数，从南到北描述狮子的觅食能力值 \(A[i]\)。此后 \(M\) 行，每行描述一次投喂：\(i,j,k\) 表示在第某次投喂中，小H选择了区间 \([i,j]\) 内觅食能力值第 \(k\) 强的狮子进行投喂。

【输出格式】

　　输出有 \(M\) 行，每行一个整数，第 \(i\) 行的整数表示在第 \(i\) 次投喂中吃到食物的狮子的觅食能力值。

【输入输出样例】

　Input

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

　Output

3
2

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(1≤m≤500000\)，\(0≤A[i]≤2*10^9\)

【来源】

　　Mr.he