Problem Description

Mario Party is a classic board game featuring numerous minigames. In this game, players possess coins and aim to collect stars at particular positions. For simplicity, we treat the board as a $1$ by $n$ grid with grids labeled with $1$ to $n$ from left to right, and there is an integer $a_i$ in cell $i$. Suppose a player is currently in the cell $i$ with $x$ coins. He may perform the following operation:
<ol>
<li> Move to cell $i+1$, and the number of coins he possesses becomes $x + a_{i+1}$ if $x+a_{i+1} \ge 0$, and remains the same otherwise . </li>
</ol>

You have to answer $q$ independent queries of the following form:
<ol>
<li> Suppose a player is currently in cell $l$ with $x$ coins. Compute the number of coins he possesses after he travels to cell $r$ by performing the above operations $r-l$ times. </li>
</ol>

Input

The first line contains an integer $T$ ($1 \le T \le 4$), denoting the number of test cases.

For each test case, the first line contains two integers $n,q$ ($1 \le n,q \le 5 \cdot 10^5$), denoting the number of cells in the grid and the number of queries, respectively.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($\sum_{i=1}^n |a_i| \le 10^6$).

Each of the following $q$ lines contains integers $l_i,r_i,x_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \le 10^{6}$), denoting the parameters of the $i$-th query.

Output

For each query in each test case, output an integer in one line, denoting the answer.

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

8
5
8
5
6
7