P1533 Poor Dogs

Xiao Ka has $n$ dogs. Because of different breeds and ages, each dog has a different beauty value. The beauty value is inversely related to how pretty a dog is (the lower the beauty value, the prettier). At mealtime, the dogs stand in a line in order, waiting for their owner to give them food. But Jiajia is really lazy; he refuses to feed so many dogs. Each time, he only feeds the dog that is the $k$-th most beautiful among the $i$-th to the $j$-th dogs (how heartless!). Moreover, to ensure that no single dog is fed too many times, none of the intervals $[i, j]$ contains another.

The first line contains two integers $n,m$, where $m$ is the number of times Jiajia feeds the dogs. The second line contains $n$ integers, where the $i$-th dog's beauty value is $a_i$. The next $m$ lines each contain $3$ integers $i,j,k$, asking for the beauty value of the dog that is the $k$-th most beautiful among the dogs from $i$ to $j$.

$m$ lines, each containing one integer, which is the beauty value of the dog fed each time.

Constraints: $1\le n \le 3\times 10^5 ,1\le m \le5\times10^4,0\le a_i