Levko 非常喜欢由整数组成的数组 a1, a2, ... , an。这就是 Levko 处理数组 a 的原因,用它执行各种操作。 Levko 执行的每个操作属于以下两种类型之一:
1. 将 li 到 ri 的所有元素增加 di。换句话说,对满足不等式li ≤ j ≤ ri的所有j执行赋值aj = aj + di。
2. 求 li 到 ri 中元素的最大值。即计算值 $$m_i = \max_{j=l_i}^{r_i} a_j$$。
遗憾的是,Levko 最近失去了他的阵列。幸运的是,Levko 记录了他对数组 a 执行的所有操作。帮助Levko,给定操作记录,找到至少一个合适的数组。给定数组的所有操作的结果必须与记录结果一致。 Levko清楚地记得他的数组中所有数字的绝对值都不超过109,所以他要求你找到这样一个数组。
输入
第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 5000) — 相应地,数组的大小和 Levko 记录中的操作数。
接下来m行描述操作,第i行描述第i个操作。第 i 行中的第一个整数是描述操作类型的整数 ti (1 ≤ ti ≤ 2)。如果 ti = 1,则后面跟着三个整数 li、ri 和 di (1 ≤ li ≤ ri ≤ n,- 104 ≤ di ≤ 104)——第一类操作的描述。如果ti = 2,则后面跟着三个整数li、ri 和mi (1 ≤ li ≤ ri ≤ n,- 5·107 ≤ mi ≤ 5·107)——第二类操作的描述。
这些操作按照 Levko 在其数组上执行的顺序给出。
输出
如果解存在,则在第一行打印“YES”(不带引号),否则打印“NO”(不带引号)。
如果解存在,则在第二行打印 n 个整数 a1, a2, ... , an (|ai| ≤ 109) — 恢复后的数组。
示例
输入 #1
4 5 1 2 3 1 2 1 2 8 2 3 4 7 1 1 3 3 2 3 4 8
输出 #1
YES 4 7 4 7
输入 #2
4 5 1 2 3 1 2 1 2 8 2 3 4 7 1 1 3 3 2 3 4 13
输出 #2
NO