Bajtocy 是二进制序列的鉴赏家。对于给定的二进制序列 $a_1, a_2, \dots, a_s$ 以及一个非负整数 $k$，我们将该序列的 $k$-近似定义为满足以下条件的任意二进制序列 $b_1, b_2, \dots, b_s$：

1. 对于 $1 \le i \le s$，满足 $0 \le b_i \le a_i \le 1$；
2. 满足 $b_i \neq b_{i+1}$ 的位置 $1 \le i \le s-1$ 的数量最多为 $k$；
3. 和 $b_1 + b_2 + \dots + b_s$ 最大。

Bajtocy 有一个他最喜欢的二进制序列 $x_1, x_2, \dots, x_S$。由于该序列可能非常长，它以压缩方式给出，即 $n$ 个正整数 $d_1, d_2, \dots, d_n$。这意味着整个序列以 $d_1$ 个 $1$ 开头，接着是 $d_2$ 个 $0$，然后是 $d_3$ 个 $1$，依此类推。更正式地说，整个序列为 $1^{d_1} 0^{d_2} 1^{d_3} \dots$。

请帮助 Bajtocy 确定他最喜欢的序列中某些连续片段的近似值。为此，你需要回答一系列查询。每个查询由一个整数 $k$ 以及两个整数 $l$ 和 $r$ 描述。这意味着你的任务是确定序列 $x_l, x_{l+1}, \dots, x_r$ 的 $k$-近似的元素之和。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 1\,000\,000$)，分别表示序列描述的长度和查询的数量。输入的第二行包含 $n$ 个正整数 $d_1, d_2, \dots, d_n$ ($1 \le S \le 10^9$，其中 $S = d_1 + d_2 + \dots + d_n$)，表示 Bajtocy 序列中连续块的长度。

接下来的 $q$ 行描述了后续的查询。第 $i$ 行包含三个整数 $l_i, r_i, k_i$ ($1 \le l_i \le r_i \le S, 0 \le k_i \le 10^9$)，表示询问序列 $x_{l_i}, x_{l_i+1}, \dots, x_{r_i}$ 的 $k_i$-近似的元素之和。

输出格式

输出 $q$ 行。第 $i$ 行应包含一个整数，表示序列 $x_{l_i}, x_{l_i+1}, \dots, x_{r_i}$ 的 $k_i$-近似的元素之和。

样例

输入 1

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

输出 1

3
3
0
3
2

说明 1

Bajtocy 最喜欢的序列是 $1, 0, 1, 1, 0, 1, 1$。共有五个查询： 1. 第一个查询是关于片段 $1, 0, 1, 1$ 的 $2$-近似。在这种情况下，该片段本身就是其 $2$-近似，结果为其和，即 $3$。 2. 第二个查询是关于同一片段的 $3$-近似。该片段同样是其 $3$-近似。 3. 第三个查询是关于片段 $0, 1, 1, 0, 1$ 的 $0$-近似。所求的 $0$-近似是常数序列 $0, 0, 0, 0, 0$，和为 $0$。 4. 第四个查询是关于整个序列的 $2$-近似。所求的 $2$-近似是序列 $1, 0, 0, 0, 0, 1, 1$，和为 $3$。 5. 第五个查询是关于片段 $1, 1, 0, 1, 1$ 的 $1$-近似。存在两个可能的 $1$-近似：$1, 1, 0, 0, 0$ 和 $0, 0, 0, 1, 1$，两者的和均为 $2$。

子任务

测试集分为以下子任务。每个子任务的测试由一组或多组独立的测试用例组成。