| The 2026 ICPC Belarus Qualification |
|---|
| Закончено |
Даны $$$m$$$ предполагаемых ответов на запросы суммы на отрезке бинарного (то есть состоящего только из нулей и единиц) массива из $$$n$$$ чисел $$$a_1, a_2, \ldots, a_n$$$: каждый ответ $$$(\ell, r, s)$$$ означает, что $$$a_\ell + a_{\ell + 1} + \ldots + a_r = s$$$.
Найдите какой-нибудь бинарный массив, удовлетворяющий всем ответам. Массив не обязательно определяется однозначно; если существует несколько массивов, найдите любой. Ответы на запросы могут противоречить друг другу, тогда необходимо сказать, что искомого массива нет.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leqslant n \leqslant 5000$$$, $$$0 \leqslant m \leqslant 2 \cdot 10^5$$$) — количество элементов в массиве и количество результатов запросов суммы.
Следующие $$$m$$$ строк содержат по три целых числа $$$\ell$$$, $$$r$$$, $$$s$$$ ($$$1 \leqslant \ell \leqslant r \leqslant n$$$, $$$0 \leqslant s \leqslant r - \ell + 1$$$), что означает, что сумма на отрезке $$$[\ell, r]$$$ должна быть равна $$$s$$$.
Если подходящего массива не существует, выведите слово NO.
В противном случае выведите в первой строке слово YES, а во второй строке — $$$n$$$ целых чисел, каждое из которых равно $$$0$$$ или $$$1$$$: любой массив, удовлетворяющий всем запросам.
Слова YES и NO можно выводить в любом регистре.
4 21 3 22 4 1
YES 1 0 1 0
5 31 4 12 5 35 5 1
NO
В первом примере также подходит массив $$$(1, 1, 0, 0)$$$.
Во втором примере можно показать, что первые два результата противоречат друг другу, а это значит, что искомого массива нет.
| Название |
|---|


