Mario Party 是一款经典的棋盘游戏，包含许多小游戏。在这个游戏中，玩家拥有金币，目标是在特定位置收集星星。为简化起见，我们将棋盘视为一个 $1 \times n$ 的网格，格子从左到右编号为 $1$ 到 $n$，且第 $i$ 个格子中有一个整数 $a_i$。假设玩家当前位于第 $i$ 个格子，拥有 $x$ 枚金币。他可以执行以下操作：

移动到第 $i+1$ 个格子，如果 $x + a_{i+1} \ge 0$，则他拥有的金币数量变为 $x + a_{i+1}$；否则，金币数量保持不变。

你需要回答 $q$ 个独立的查询，形式如下：

假设玩家当前位于第 $l$ 个格子，拥有 $x$ 枚金币。计算他通过执行上述操作 $r - l$ 次到达第 $r$ 个格子后，所拥有的金币数量。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 4$)，表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n, q$ ($1 \le n, q \le 5 \cdot 10^5$)，分别表示网格中的格子数量和查询数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($\sum_{i=1}^n |a_i| \le 10^6$)。

接下来的 $q$ 行，每行包含三个整数 $l_i, r_i, x_i$ ($1 \le l_i \le r_i \le n, 0 \le x_i \le 10^6$)，表示第 $i$ 个查询的参数。

输出格式

对于每个测试用例中的每个查询，输出一行一个整数，表示答案。

样例

输入 1

1
5 6
1 -2 3 -4 5
1 5 0
1 5 1
1 5 2
1 5 3
1 5 4
1 5 5

输出 1

8
5
8
5
6
7