Levko 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 $m_{i} = \operatorname{max}_{j = l_{i}}^{r_{i}} a_{j}$. 

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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Implementation

Greedy algorithms


Solutions:
(n, m) = map(int, input().split())
a = [10 ** 9 for _ in range(n)]
extra = [0 for _ in range(n)]
query = list()
for _ in range(m):
	(t, l, r, x) = map(int, input().split())
	l -= 1
	r -= 1
	query.append((t, l, r, x))
	if t == 1:
		for j in range(l, r + 1):
			extra[j] += x
	else:
		for j in range(l, r + 1):
			a[j] = min(a[j], x - extra[j])
extra = a.copy()
for (t, l, r, x) in query:
	if t == 1:
		for j in range(l, r + 1):
			a[j] += x
	else:
		val = -10 ** 9
		for j in range(l, r + 1):
			val = max(val, a[j])
		if not val == x:
			print('NO')
			return
print('YES')
for x in extra:
	print(x, end=' ')


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 10 ** 9 + 7
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
(n, m) = Ri()
lis = []
for i in range(m):
	lis.append(Ri())
ans = [10 ** 9] * n
for i in range(m - 1, -1, -1):
	if lis[i][0] == 2:
		for j in range(lis[i][1] - 1, lis[i][2]):
			ans[j] = min(ans[j], lis[i][3])
	else:
		for j in range(lis[i][1] - 1, lis[i][2]):
			if ans[j] != 10 ** 9:
				ans[j] -= lis[i][3]
for i in range(n):
	if ans[i] == 10 ** 9:
		ans[i] = -10 ** 9
temp = ans[:]
flag = True
for i in range(m):
	if lis[i][0] == 2:
		t = -10 ** 9
		for j in range(lis[i][1] - 1, lis[i][2]):
			t = max(t, temp[j])
		if t != lis[i][3]:
			flag = False
			break
	else:
		for j in range(lis[i][1] - 1, lis[i][2]):
			temp[j] += lis[i][3]
if flag:
	YES()
	print(*ans)
else:
	NO()