Ovuvuevuevue Enyetuenwuevue Ugbemugbem Osas accidentally found an undiscovered tomb. He successfully sneaked in without triggering any traps. When he finally got into the treasure room, he found a note that warns tomb raiders about the trap in the treasure room. Osas arranged the note and concluded some rules:
- The treasure room has n treasure crates, each crate has its value. The values are sorted in descending order.
- There are several intervals [l,r] on the note.
- Tomb raiders must loot less than or equal to m treasure crates in the correct interval, where m is a number that Osas have to guess.
- If any tomb raider loot more than m treasure crates or loot any crate that not in the interval, the trap would trigger and kill that tomb raider! Osas doesn't want to die here.
Osas wants these treasures, but he doesn't want to die. Osas wants to know if he pick one interval and guess a number as "m", what is the maximum value he could loot? Osas asks you for help!
Osas will give you the value of every treasure crate and the number he would like to guess, you need to write a program to help him.
The input contains exactly one testcase.
The first line contains two integers n, q. q indicates the amount of queries of (l,r,m).
The next line is the sequence of values of n treasure crates, each seperated by a space.
The next q lines, each line contains exactly three integers l, r, m.
1<=m<=n<=106, 1<=q<=106, 1<=l<=r<=n, m<=r-l+1, the value of every treasure crate won't larger than 105 or smaller than -105. All of the values are integers. Notice that the value could be negative, and Osas can choose nothing.
Note that the sequence index starts from 1. For example: for a sequence "a": "3 4 5 6 7", a[4]=6, a[1]=3.
For each query, output the maximum value Osas could get. Each query holds exactly one line.
Remember to print a '\n' at the end of the output.