어떤 수열 $B_{1 \dots m}$에 대하여, 다음 두 조건을 만족하는 수열 $C_{1 \dots k}$가 존재할 때, $W$를 $k$-best number라고 부릅니다.

1. $C_{1 \dots k}$는 $B_{1 \dots m}$의 부분 수열이다.
2. 모든 $i \in [1, k]$에 대하여, $C_i + C_{(i \bmod k) + 1} \le W$이다.

수열 $A_{1 \dots n}$이 주어질 때, $Q$개의 질문에 답해야 합니다. 각 질문은 세 정수 $L, R, K$로 구성되며, $A_{L \dots R}$의 최소 $K$-best number를 계산해야 합니다.

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

입력

첫 번째 줄에는 두 정수 $n$과 $Q$ ($1 \le n, Q \le 10^5$)가 주어집니다. 두 번째 줄에는 $n$개의 정수 $A_{1 \dots 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$).

출력

각 질문에 대하여, 답인 정수 하나를 한 줄에 출력합니다.

예제

입력 1

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

출력 1

8
3
6