J. Sumotonic Sequences
time limit per test
7 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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$$$).

Input

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

Output

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.

Example
Input
1
5 2
5 8 5 2 4
5 5 6 6
2 4 1 3
Output
NO
NO
YES