#P18336. Sumotonic Sequences

Sumotonic Sequences

Sumotonic Sequences

一个整数序列称为单调的,当且仅当它是非递减序列或者非递增序列。

一个序列称为 sumotonic,当且仅当它能表示为任意多个只含非负值的单调序列的逐项和。这些单调序列与原序列长度相同,每个序列可以选择自己的单调方向。

给定序列 A=(a1,…,an)A=(a_1,\ldots,a_n) 和 kk 次操作。每次操作向 AA 的一个连续区间加上等差数列:对于给定的 p,q,s,dp,q,s,d,将

ap,ap+1,…,aqa_p,a_{p+1},\ldots,a_q

分别改为

ap+s, ap+1+s+d, …, aq+s+(q−p)d.a_p+s,\ a_{p+1}+s+d,\ \ldots,\ a_q+s+(q-p)d.

判断初始序列以及每次操作后的序列是否为 sumotonic。操作会永久生效,后续操作在之前的修改结果上继续进行。

输入格式

第一行包含测试用例数 ZZ。

每组测试用例的第一行包含两个整数 n,kn,k,分别表示序列长度和操作次数。

第二行包含序列的初始值 a1,…,ana_1,\ldots,a_n。

接下来 kk 行,每行包含四个整数 p,q,s,dp,q,s,d,表示向区间 [p,q][p,q] 加上首项为 ss、公差为 dd 的等差数列。

输出格式

对每组测试用例输出 k+1k+1 行。

第一行表示初始序列的答案;此后第 ii 行表示第 i−1i-1 次操作后的答案。

如果相应序列是 sumotonic,则输出 YES,否则输出 NO。

数据范围

  • 1≤Z≤100001\le Z\le10000;
  • 2≤n≤2000002\le n\le200000;
  • 1≤k≤2000001\le k\le200000;
  • 初始 1≤ai≤2⋅1091\le a_i\le2\cdot10^9;
  • 每次操作 1≤p≤q≤n1\le p\le q\le n;
  • 每次操作 1≤s,d≤100001\le s,d\le10000;
  • 所有测试用例的 n+kn+k 之和不超过 400000400000。

s,ds,d 始终为正数。aia_i 的上界限制的是初始值,操作后的数值可以超过 2⋅1092\cdot10^9。当 p=qp=q 时,只给一个元素加上 ss,公差 dd 不影响这一操作的结果。

样例输入 1

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

样例输出 1

NO
NO
YES