Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. Levko and Array Recovery

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputLevko loves array *a*_{1}, *a*_{2}, ... , *a*_{n}, 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:

- Increase all elements from
*l*_{i}to*r*_{i}by*d*_{i}. In other words, perform assignments*a*_{j}=*a*_{j}+*d*_{i}for all*j*that meet the inequation*l*_{i}≤*j*≤*r*_{i}. - Find the maximum of elements from
*l*_{i}to*r*_{i}. 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 10^{9} 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 *t*_{i} (1 ≤ *t*_{i} ≤ 2) that describes the operation type. If *t*_{i} = 1, then it is followed by three integers *l*_{i}, *r*_{i} and *d*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*, - 10^{4} ≤ *d*_{i} ≤ 10^{4}) — the description of the operation of the first type. If *t*_{i} = 2, then it is followed by three integers *l*_{i}, *r*_{i} and *m*_{i} (1 ≤ *l*_{i} ≤ *r*_{i} ≤ *n*, - 5·10^{7} ≤ *m*_{i} ≤ 5·10^{7}) — 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 *a*_{1}, *a*_{2}, ... , *a*_{n} (|*a*_{i}| ≤ 10^{9}) — 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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/28/2022 12:38:59 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|