Nhiệm vụ của bạn là xây dựng một mảng \(x_1,x_2,\dots,x_n\) gồm \(n\) số nguyên.

Mảng phải thỏa mãn \(m\) ràng buộc có dạng \((l,r,s)\): tổng \(x_l + x_{l+1} + \dots + x_r\) phải bằng \(s\).

Đầu vào

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): độ dài của mảng và số lượng ràng buộc.

\(m\) dòng tiếp theo, mỗi dòng chứa ba số nguyên \(l\), \(r\) và \(s\): mô tả các ràng buộc.

Đầu ra

Nếu tồn tại lời giải, in YES trên dòng đầu tiên.

Trên dòng thứ hai, in \(n\) số nguyên \(x_1, x_2,\dots, x_n\): các phần tử của mảng. Tất cả phần tử của mảng phải thỏa mãn \(-10^{15} \le x_i \le 10^{15}\) và mảng phải thỏa mãn tất cả các ràng buộc đã cho. Bạn có thể in bất kỳ lời giải hợp lệ nào.

Nếu không tồn tại lời giải, chỉ in 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

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

YES
0 2 1 -1 3