403881: GYM101350 L All’s Wall That Ends Wall

In the magical forest, you come upon N walls that you think is a great place to store water for your animal friends. The i^th wall consists of a_i blocks stacked on top of each other.

Your job is to answer queries of two types:

- For queries of the first type, print the amount of water that could be stored between all the walls.

- For queries of the second type, increase the number of blocks on the x^th wall by v.

The first line of input is T – the number of test cases.

The first line of each test case is integers N and Q (1 ≤ N, Q ≤ 10⁵).

The second line contains N space-separated integers a_i (1 ≤ a_i ≤ 10⁵).

The next Q lines contain either ‘P’ – denoting a query of the first type, or ‘U’ followed by x and v – denoting a query of the second type (1 ≤ x ≤ N) (1 ≤ v ≤ 10⁴).

For each test case and query of the first type, output on a line the amount of water that could be stored between the walls.

1
6 3
2 1 4 2 1 3
P
U 1 2
P

4
6