8654: Mario Party

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_iai in cell $i$. Suppose a player is currently in the cell $i$ with $x$ coins. He may perform the following operation:

1. Move to cell i+1, and the number of coins he possesses becomes  x+ai+1 if x+ai+1≥0, and remains the same otherwise .

You have to answer q independent queries of the following form:

1. 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.

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≤n,q≤5⋅105), denoting the number of cells in the grid and the number of queries, respectively.

The second line of each test case contains n integers a1,a2,…,an (∑i=1n∣ai∣≤106).

Each of the following q lines contains integers li,ri,xi (1≤li≤ri≤n, 0≤xi≤106), denoting the parameters of the i-th query.

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