Your task is to construct an array $x_1,x_2,\dots,x_n$ consisting of $n$ integers.

The array must satisfy $m$ constraints of the form $(l,r,s)$: the sum $x_l + x_{l+1} + \dots + x_r$ must equal $s$.

Input

The first line has two integers $n$ and $m$: the length of the array and the number of constraints.

The next $m$ lines each have three integers $l$, $r$ and $s$: the description of the constraints.

Output

If a solution exists, print YES on the first line.

On the second line, print $n$ integers $x_1, x_2,\dots, x_n$: the contents of the array. All elements of the array must satisfy $-10^{15} \le x_i \le 10^{15}$ and the array must satisfy all given constraints. You can print any valid solution.

If no solution exists, just print NO.

Constraints

• $1 \le n \le 5000$
• $0 \le m \le 2 \cdot 10^5$
• $1 \le l \le r \le n$
• $-10^9 \le s \le 10^9$

Example

Input:

5 3
1 3 3
3 5 3
4 4 -1

Output:

YES
0 2 1 -1 3