A sequence of integers is called monotonic if it is either nondecreasing or nonincreasing. A sequence is sumotonic if it can be expressed as a sum of any number of monotonic sequences, all having only non-negative values.
You are given a sequence $$$A = (a_1, \ldots, a_n)$$$ and a list of $$$k$$$ operations. Each operation adds an arithmetic sequence to some segment of $$$A$$$. More precisely, for a given interval $$$[p,q]$$$ and integers $$$s$$$ and $$$d$$$, the elements $$$a_p, a_{p+1}, \ldots, a_q$$$ are changed to $$$a_p + s, a_{p+1} + s + d, \ldots, a_q + s + (q-p)\cdot d$$$.
Determine if $$$A$$$ is sumotonic, for the initial sequence and after each operation. Note that the operations are persistent (they have a permanent effect on the sequence $$$A$$$).
The first line of input contains the number of test cases $$$Z$$$ ($$$1 \leq Z \leq 10\,000$$$). The descriptions of the test cases follow.
The first line of each test case contains integers $$$n$$$ and $$$k$$$ ($$$2 \leq n \leq 200\,000$$$, $$$1 \leq k \leq 200\,000$$$) – the length of the sequence and the number of operations respectively.
The second line contains initial elements $$$a_1, \ldots, a_n$$$ of the sequence $$$A$$$ ($$$1 \leq a_i \leq 2 \cdot 10^9$$$ for $$$i = 1, 2, \ldots, n$$$).
The last $$$k$$$ lines contain operations, each described by four integers $$$p, q, s, d$$$ ($$$1 \leq p \leq q \leq n$$$, $$$1 \leq s, d \leq 10\,000$$$), meaning that to the interval $$$[p, q]$$$ we add an arithmetic sequence with starting element $$$s$$$ and difference $$$d$$$.
The sum of $$$n+k$$$ over all test cases does not exceed $$$400\,000$$$.
For each test case, output $$$k+1$$$ lines. The first one should contain the text "YES" if the initial sequence is sumotonic, "NO" otherwise. Each of the remaining $$$k$$$ lines should similarly describe the state of the sequence after every operation.
1 5 2 5 8 5 2 4 5 5 6 6 2 4 1 3
NO NO YES
