최선 부분 수열

수열 $B\_{1...m}$에 대해, 다음 두 조건을 만족하는 수열 $C\_{1...k}$가 존재하면 $W$를 $B$의 $k$-best number라고 부른다.

1. $C\_{1...k}$는 $B\_{1...m}$의 부분 수열이다.
2. $\forall i \in \[1, k], C\_{i} + C\_{(i \bmod k) + 1} \le W$.

수열 $A\_{1...n}$이 주어진다. $Q$개의 질의에 답하라. 각 질의는 세 정수 $L, R, K$로 이루어지며, $A\_{L...R}$의 최소 $K$-best number를 구해야 한다.

수열 $C$가 $B$의 부분 수열이라는 것은, $B$에서 일부 원소(없거나 전부일 수도 있음)를 제거해 $C$를 얻을 수 있다는 뜻이다.

첫 줄에 두 정수 $n$, $Q$ ($1 \le n, Q \le 10^5$)가 주어진다.

둘째 줄에는 $n$개의 정수 $A\_{1...n}$ ($0 \le A\_i \le 10^9$)이 주어진다.

이후 $Q$개의 줄에 각각 질의를 나타내는 세 정수 $L, R, K$ ($1 \le L \le R \le n$; $1 \le K \le R - L + 1$)가 주어진다.

각 질의마다 답을 한 줄에 하나씩 출력한다.