Bajtocy is a connoisseur of binary sequences. For a given binary sequence $a_1, a_2, \dots, a_s$ and a non-negative integer $k$, we call a $k$-approximation of this sequence any binary sequence $b_1, b_2, \dots, b_s$ satisfying the following conditions:

1. $0 \le b_i \le a_i \le 1$ for $1 \le i \le s$, and
2. the number of positions $1 \le i \le s - 1$ for which $b_i \neq b_{i+1}$ is at most $k$, and
3. the sum $b_1 + b_2 + \dots + b_s$ is as large as possible.

Bajtocy has his favorite binary sequence $x_1, x_2, \dots, x_S$. Since this sequence can be very long, it is given in a compressed form as a sequence of $n$ positive integers $d_1, d_2, \dots, d_n$. This means that the entire sequence starts with a block of $d_1$ ones, followed by a block of $d_2$ zeros, a block of $d_3$ ones, and so on. More formally, the entire sequence is $1^{d_1} 0^{d_2} 1^{d_3} \dots$.

Help Bajtocy determine the approximations of some contiguous fragments of his favorite sequence. To do this, you should answer a series of queries. Each query is described by an integer $k$ and two integers $l$ and $r$. They mean that your task is to determine the sum of the sequence that is a $k$-approximation of the sequence $x_l, x_{l+1}, \dots, x_r$.

Input

The first line of input contains two integers $n$ and $q$ ($1 \le n, q \le 1\,000\,000$), representing the length of the sequence description and the number of queries, respectively. The second line of input contains $n$ positive integers $d_1, d_2, \dots, d_n$ ($1 \le S \le 10^9$, where $S = d_1 + d_2 + \dots + d_n$) representing the lengths of consecutive blocks in Bajtocy's sequence.

The next $q$ lines describe the subsequent queries. The $i$-th of these contains three integers $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le S, 0 \le k_i \le 10^9$) indicating that we are asking for the sum of the $k_i$-approximation of the sequence $x_{l_i}, x_{l_i+1}, \dots, x_{r_i}$.

Output

You should print $q$ lines. The $i$-th line should contain a single integer representing the sum of the $k_i$-approximation of the sequence $x_{l_i}, x_{l_i+1}, \dots, x_{r_i}$.

Examples

Input 1

5 5
1 1 2 1 2
1 4 2
1 4 3
2 6 0
1 7 2
3 7 1

Output 1

3
3
0
3
2

Note

Bajtocy's favorite sequence is $1, 0, 1, 1, 0, 1, 1$. There are five queries: 1. The first query is for a 2-approximation of the fragment $1, 0, 1, 1$. In this case, the fragment itself is its own 2-approximation, and the result is its sum, which is 3. 2. The second query is for a 3-approximation of the same fragment. This fragment is also its own 3-approximation. 3. The third query is for a 0-approximation of the fragment $0, 1, 1, 0, 1$. The sought 0-approximation is the constant sequence $0, 0, 0, 0, 0$, with a sum of 0. 4. The fourth query is for a 2-approximation of the entire sequence. The sought 2-approximation is the sequence $1, 0, 0, 0, 0, 1, 1$, with a sum of 3. 5. The fifth query is for a 1-approximation of the fragment $1, 1, 0, 1, 1$. There are two possible 1-approximations, $1, 1, 0, 0, 0$ and $0, 0, 0, 1, 1$, both with a sum of 2.

Subtasks