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.
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$$$.
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.
4 21 3 22 4 1
YES 1 0 1 0
5 31 4 12 5 35 5 1
NO
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.