A version with an increased time limit is available at: https://qoj.ac/problem/3576

Given $n$ slimes arranged in a row, the size of the $i$-th slime is $a_i$.

For a set of slimes, a game can be played: given a non-negative integer $k$, the $i$-th slime can eat the $j$-th slime if and only if $a_i - a_j \ge k$. When this happens, the $j$-th slime is removed and $a_i$ becomes $a_i + a_j$. Slimes can eat each other in any order. The game ends when no slime can eat any other slime. If exactly one slime remains, that slime wins; otherwise, no slime wins.

There are $q$ queries, each given by $l, r, k$. For each query, determine how many slimes in the range $[l, r]$ could potentially win the game.

Note that each query is independent, meaning no slimes are actually consumed during the query process.

Input

The first line contains two positive integers $n$ and $q$.

The second line contains $n$ positive integers $a_1, \dots, a_n$.

The following $q$ lines each contain two positive integers $l, r$ and a non-negative integer $k$, representing a query.

Output

Output $q$ lines, each containing a non-negative integer representing the answer to the corresponding query.

Examples

Input 1

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

Output 1

5
1
1
0

Note 1

For the second query: $k=4$, the slimes with sizes $3, 7, 5$ play the game. The slime with size $7$ can first eat the slime with size $3$, becoming size $10$, and then eat the slime with size $5$ to win. It can be proven that the slimes with sizes $3$ and $5$ cannot win.

Input 2

3 2
3 3 3
1 3 1
1 3 0

Output 2

0
3

Input 3

See the provided files; this sample satisfies the constraints of subtask $6$.

Constraints

For all data, $2 \le n \le 2 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$, $1 \le a_i \le 10^9$, $1 \le l \le r \le n$, $0 \le k \le 10^9$.