南京有一个很大的野生动物园。
这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成 N个区域，每个区域都饲养着一头狮子。
这些狮子从北到南编号为 1,2,3,…,N。每头狮子都有一个觅食能力值 Ai，Ai越小觅食能力越强。
饲养员西西决定对狮子进行M次投喂，每次投喂都选择一个区间 [I,J]，从中选取觅食能力值第 K强的狮子进行投喂。
值得注意的是，西西不愿意对某些区域进行过多的投喂，他认为这样有悖公平。
因此西西的投喂区间是互不包含的(即区间 [1,10]不会与 [3,4]或 [5,10]同时存在，但可以与 [9,11]或 [10,20]一起)。
同一区间也只会出现一次。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。

第一行，两个整数 N,M。
第二行，N个整数 Ai。(1≤Ai≤2³¹−1)。
此后 M行，每行描述一次投喂。第 t+2行的三个数 I,J,K表示在第 t次投喂中，西西选择了区间 [I,J]内觅食能力值第 K强的狮子进行投喂。

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

对于 100%的数据，有 1≤N≤10⁵,1≤M≤5×10⁴。

数据结构 线段树 树状数组