ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5906: Levko and Array Recovery

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：4 通过：3
提交提交记录统计Web Board

题目描述

列夫科爱阵列一个a1，a2,... ,an，由整数组成，非常多。这就是为什么 Levko 玩数组 a 并用它执行各种操作的原因。Levko 执行的每个操作都有两种类型之一：

1. 增加所有元素从li自ri由di。我.换句话说，执行分配一个aj=aj+di对于所有满足不等式的li<=j<=ri。

2. 从中查找最大元素数li自ri.也就是说，计算值。.

可悲的是，列夫科最近失去了他的阵列。幸运的是，Levko 有他在阵列 a 上执行的所有操作的记录。根据操作记录，帮助 Levko 找到至少一个合适的阵列。给定数组的所有操作的结果必须与记录结果一致。列夫科清楚地记得，他的数组中的所有数字都没有超过109在它们的绝对值中，所以他要求你找到这样一个数组。
Levko loves array a1,a2,... ,an, consisting of integers, very much. That is why Levko is playing with array a, performing all sorts of operations with it. Each operation Levko performs is of one of two types:

  1. Increase all elements from li to ri by di. In other words, perform assignments aj=aj+di for all j that meet the inequation li≤j≤ri.
  2. Find the maximum of elements from li to ri. That is, calculate the value .
Sadly, Levko has recently lost his array. Fortunately, Levko has records of all operations he has performed on array a. Help Levko, given the operation records, find at least one suitable array. The results of all operations for the given array must coincide with the record results. Levko clearly remembers that all numbers in his array didn't exceed 109 in their absolute value, so he asks you to find such an array.
Input
The first line contains two integers n and m (1≤n,m≤5000) − the size of the array and the number of operations in Levko's records, correspondingly.
Next m lines describe the operations, the i-th line describes the i-th operation. The first integer in the i-th line is integer ti (1≤ti≤2) that describes the operation type. If ti=1, then it is followed by three integers li, ri and di (1≤li≤ri≤n, -104≤di≤104) − the description of the operation of the first type. If ti=2, then it is followed by three integers li, ri and mi (1≤li≤ri≤n, -5·107≤mi≤5·107) − the description of the operation of the second type.
The operations are given in the order Levko performed them on his array.
Output
In the first line print "YES" (without the quotes), if the solution exists and "NO" (without the quotes) otherwise.
If the solution exists, then on the second line print n integers a1,a2,... ,an (|ai|≤109) − the recovered array.
Examples
Input 
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 8
Output 
YES
4 7 4 7
Input 
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 13
Output 
NO

输入格式

第一行包含两个整数 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)− 恢复的阵列。
Input 

4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 8
Output 
YES
4 7 4 7
Input 
4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 13
Output 
NO

输入样例 复制 

4 5
1 2 3 1
2 1 2 8
2 3 4 7
1 1 3 3
2 3 4 13

输出样例 复制 

NO

分类标签