题目描述

在鄂尔多斯青青的草原上，有一群小肥羊。它们之所以胖胖的，是因为它们不单吃草还吃花。已知草地上散落着 n 朵鲜花（$1 ≤ n < 10^5$ 且 n 为奇数），每朵鲜花上都有一个独特的数字 $a_i$（$1 ≤ a_i < 10^9$）。小肥羊见花就吃，影响了津津、菲菲和皮皮 3 人欣赏草原景色，他们非常生气地对小肥羊们说：你们只能吃一块草地中数字第 k 小的那朵（最小的数是第 0 小），否则我们就把你们烤了串。小肥羊们害怕了，但是它们不会算数，只能请津津、菲菲和皮皮帮忙指出哪些花能吃。

输入格式

第一行两个正整数 N，M。
第二行 N 个数，表示序列 $A_1,A_2,...,A_N$。
紧接着的 M 行，每行三个正整数 i,j,k（k ≤ j-i+1），表示询问 $A_i...A_j$ 中第 k 小的数等于多少。

输出格式

共输出 M 行，第 i 行输出第 i 个询问的答案。

样例

输入样例 #1

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

输出样例 #1

1
3
4