← 返回题目列表

Codeforces · 360/A

A. Levko 和阵列恢复

中文机器翻译题面 查看原题

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