如果一个整数序列是单调不减或单调不增的，则称其为单调序列。如果一个序列可以表示为任意数量的单调序列之和，且这些单调序列的所有项均为非负值，则称该序列为 sumotonic 序列。

给定一个序列 $A = (a_1, \dots, a_n)$ 和 $k$ 个操作。每个操作都会向 $A$ 的某个区间添加一个等差数列。更具体地说，对于给定的区间 $[p, q]$ 以及整数 $s$ 和 $d$，元素 $a_p, a_{p+1}, \dots, a_q$ 将分别变为 $a_p + s, a_{p+1} + s + d, \dots, a_q + s + (q - p) \cdot d$。

请判断初始序列以及每次操作后的序列是否为 sumotonic 序列。注意，这些操作是持久的（它们对序列 $A$ 有永久性的影响）。

输入格式

输入的第一行包含测试用例的数量 $Z$ ($1 \le Z \le 10\,000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含整数 $n$ 和 $k$ ($2 \le n \le 200\,000, 1 \le k \le 200\,000$)，分别表示序列的长度和操作的数量。

第二行包含序列 $A$ 的初始元素 $a_1, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^9$，$i = 1, 2, \dots, n$)。

最后 $k$ 行包含操作，每行由四个整数 $p, q, s, d$ ($1 \le p \le q \le n, 1 \le s, d \le 10\,000$) 描述，表示向区间 $[p, q]$ 添加一个首项为 $s$、公差为 $d$ 的等差数列。

所有测试用例的 $n + k$ 之和不超过 $400\,000$。

输出格式

对于每个测试用例，输出 $k + 1$ 行。第一行应包含文本 “YES”（如果初始序列是 sumotonic 的）或 “NO”（否则）。其余 $k$ 行应以相同方式描述每次操作后序列的状态。

样例

输入 1

1
5 2
5 8 5 2 4
5 5 6 6
2 4 1 3

输出 1

NO
NO
YES