0 Judge
Code: 0
You are the manager in charge of an automatic pumping station. The station consists of $N$ water sinks, each equipped with pump motors capable of drawing water from the sink. The sinks are numbered sequentially from $1$ to $N$.
After the station works automatically for a period of time, you are now investigating the log recorded by the automatic system. The log of the automatic system consists of two kinds of events described (without quotes) as follows.
"+ a" records a raining event. During the rain, each of the working sink is filled with $a$ units of water in the station.
"- x y s" records a water drawing event. Each of the working sink numbered in the range $[x, y]$ is drawn $s$ units of water. However, if there is less than $s$ units of water remained in a sink, only those amount remained in the sink will be drawn.
In order to prevent pump motors from working with an empty sink, which may damage the motors, the pumps are shut down and the sink is sealed after the first drawing event that makes the sink empty. The non-working sinks will not accept filling and drawing afterwards.
It is your task to evaluate the total amount of water actually drawn from the station by investigating the given $Q$ records of system log. all of the sinks are non-empty and in the working state at the beginning.
The first line of the input contains an integer $T$, the number of test cases. Each test case is formatted as follows.
$N\;Q$
$c_{1}\;c_{2}\;\cdots\;c_{N}$
$op_1$
$op_2$
$\vdots$
$op_Q$
The first line of each test case consists of 2 integers $N$ ($1 \leq N \leq 10^{5}$) and $Q$ ($1 \leq Q \leq 10^{5}$) representing that there are $N$ sinks and $Q$ records in the system log.
The second line contains $N$ space-separated integers $c_i$ ($1 \leq c_i \leq 10^{5}$), representing that there is $c_i$ units of water in the sink $i$ at the beginning.
$Q$ lines of the logs $op_i$ follow. If the record describes a raining event, it is formatted as follows.
The line contains a "+" sign, and an integer $a$ ($1 \leq a \leq 10^{5}$), the amount of units of water filled. If the record describes a drawing event, it is formatted as follows.
The line contains a "-" sign, and three space-separated integers $x$, $y$ ($1 \leq x \leq y \leq N$), and $s$ ($1 \leq s \leq 10^{5}$), representing the range and the amount drawn as described in the problem description.
For each test case, output an integer, which denotes the evaluated total amount of water actually drawn from the station, in a line.
4
8 5
6 7 4 2 5 5 8 8
- 3 6 4
+ 4
- 5 8 7
+ 2
- 1 8 5
7 5
3 1 3 1 3 1 3
- 1 7 2
+ 2
- 1 7 2
+ 2
- 1 7 2
15 19
13 25 20 16 13 12 3 22 5 6 7 1 2 10 10
- 1 11 5
+ 4
+ 5
- 8 12 10
- 4 7 3
- 3 7 13
- 1 4 13
+ 8
- 7 9 13
- 5 12 4
- 2 6 15
+ 10
+ 9
+ 8
- 10 15 8
+ 3
+ 1
- 7 14 2
+ 8
1 6
1
+ 1
- 1 1 1
+ 2
- 1 1 2
+ 3
- 1 1 4
58
27
280
7
no