Nazywamy $W$ liczbą $k$-najlepszą ciągu $B_{1 \dots m}$, jeśli istnieje ciąg $C_{1 \dots k}$ spełniający następujące dwa warunki:

1. $C_{1 \dots k}$ jest podciągiem $B_{1 \dots m}$.
2. $\forall i \in [1, k], C_i + C_{(i \bmod k)+1} \le W$.

Mając dany ciąg $A_{1 \dots n}$, musisz odpowiedzieć na $Q$ pytań. Każde pytanie składa się z trzech liczb całkowitych $L, R, K$ i musisz obliczyć minimalną liczbę $k$-najlepszą dla $A_{L \dots R}$.

Przypomnijmy, że $C$ jest podciągiem $B$ wtedy i tylko wtedy, gdy możemy otrzymać $C$ poprzez usunięcie pewnych elementów z $B$ (być może żadnego lub wszystkich).

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $Q$ ($1 \le n, Q \le 10^5$).

Druga linia zawiera $n$ liczb całkowitych $A_{1 \dots n}$ ($0 \le A_i \le 10^9$).

Następnie następuje $Q$ linii. Każda z nich zawiera trzy liczby całkowite $L, R, K$, reprezentujące pytanie ($1 \le L \le R \le n$; $1 \le K \le R - L + 1$).

Wyjście

Dla każdego pytania wyprowadź w pojedynczej linii jedną liczbę całkowitą: odpowiedź.

Przykład

Wejście 1

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

Wyjście 1

8
3
6