M. Binary Array and Sums
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$m$$$ answers to range sum queries on a binary (that is, consisting only of zeros and ones) array of $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$: each answer $$$(\ell, r, s)$$$ means that $$$a_\ell + a_{\ell + 1} + \ldots + a_r = s$$$.

Find any binary array that satisfies all the answers. The array is not necessarily unique; if several arrays exist, find any of them. The query answers may contradict each other, in which case you must report that no such array exists.

Input

The first line contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5000$$$, $$$0 \leq m \leq 2 \cdot 10^5$$$): the number of elements in the array and the number of range sum query results.

The next $$$m$$$ lines contain integers $$$\ell$$$, $$$r$$$, and $$$s$$$ ($$$1 \leq \ell \leq r \leq n$$$, $$$0 \leq s \leq r - \ell + 1$$$): the sum on the segment $$$[\ell, r]$$$ must equal $$$s$$$.

Output

If no suitable array exists, print NO.

Otherwise, print YES on the first line, and $$$n$$$ integers on the second line, each equal to $$$0$$$ or $$$1$$$: any array that satisfies all the queries.

You may print the words YES and NO in any case.

Examples
Input
4 2
1 3 2
2 4 1
Output
YES
1 0 1 0
Input
5 3
1 4 1
2 5 3
5 5 1
Output
NO
Note

In the first sample, the array $$$(1, 1, 0, 0)$$$ is also valid.

In the second sample, it can be shown that the first two results contradict each other, which means that no such array exists.