1073. 野生动物园

时间限制 1000 ms
内存限制 128 MB

题目描述

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

输入数据

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

输出数据

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

样例输入

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

样例输出

3
2

样例说明

对于100%的数据,有1< =N< =100000,1< =M< =50000。

题目信息

未提交
未通过无法查看
未通过无法查看