cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成$N$个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为$1,2,3,…,N$。每头狮子都有一个觅食能力值$A_i$，$A_i$越小觅食能力越强。饲养员cmdButtons决定对狮子进行$M$次投喂，每次投喂都选择一个区间$[I,J]$，从中选取觅食能力值第$K$强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此cmdButtons的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

输入第一行有两个数$N$和$M(1 \le N \le 100000，1 \le M \le 50000)$。此后一行有$N$个数，从南到北描述狮子的觅食能力值。此后$M$行，每行描述一次投喂。第$t+2$的三个数$I,J,K$表示在第$t$次投喂中，cmdButtons选择了区间$[I,J]$内觅食能力值第$K$强的狮子进行投喂。

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

7 2
1 5 2 6 3 7 4
1 5 3
2 7 1 · \n
 · · · · · · \n
 · · \n
 · · \n

3
2 \n
 \n