시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
7 초 1024 MB 5 1 1 50.000%

문제

We call $W$ a $k$-best number of sequence $B_{1...m}$ if there exists a sequence $C_{1...k}$ satisfying the following two conditions:

  1. $C_{1...k}$ is a subsequence of $B_{1...m}$.
  2. $\forall i \in [1, k], C_{i} + C_{(i \bmod k) + 1} \le W$.

Given a sequence $A_{1...n}$, you need to answer $Q$ questions. Each question consists of three integers $L, R, K$, and you need to calculate the minimum $K$-best number of $A_{L...R}$.

Recall that $C$ is a subsequence of $B$ if and only if we can obtain $C$ by removing some elements of $B$ (possibly none or all).

입력

The first line contains two integers $n$ and $Q$ ($1 \le n, Q \le 10^5$).

The second line contains $n$ integers $A_{1...n}$ ($0 \le A_i \le 10^9$).

Then $Q$ lines follow. Each of them contains three integers $L, R, K$, representing a question ($1 \le L \le R \le n$; $1 \le K \le R - L + 1$).

출력

For each question, output a single line with a single integer: the answer.

예제 입력 1

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

예제 출력 1

8
3
6