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