Chúng ta gọi $W$ là một $k$-best number của dãy $B_{1 \dots m}$ nếu tồn tại một dãy $C_{1 \dots k}$ thỏa mãn hai điều kiện sau:

1. $C_{1 \dots k}$ là một dãy con của $B_{1 \dots m}$.
2. $\forall i \in [1, k], C_i + C_{(i \bmod k)+1} \leq W$.

Cho một dãy $A_{1 \dots n}$, bạn cần trả lời $Q$ câu hỏi. Mỗi câu hỏi bao gồm ba số nguyên $L, R, K$, và bạn cần tính giá trị $k$-best number nhỏ nhất của $A_{L \dots R}$.

Nhắc lại rằng $C$ là một dãy con của $B$ khi và chỉ khi ta có thể thu được $C$ bằng cách loại bỏ một số phần tử của $B$ (có thể không loại bỏ phần tử nào hoặc loại bỏ tất cả).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $Q$ ($1 \leq n, Q \leq 10^5$). Dòng thứ hai chứa $n$ số nguyên $A_{1 \dots n}$ ($0 \leq A_i \leq 10^9$). Tiếp theo là $Q$ dòng. Mỗi dòng chứa ba số nguyên $L, R, K$, đại diện cho một câu hỏi ($1 \leq L \leq R \leq n$; $1 \leq K \leq R - L + 1$).

Dữ liệu ra

Với mỗi câu hỏi, in ra một dòng chứa một số nguyên duy nhất: kết quả.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

8
3
6