Codeforces Round #275 (Div. 1)B (Segment Tree Bit Operation)_html/css_WEB-ITnose

B. Interesting Array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

We'll call an array of n non-negative integers a[1],?a[2],?...,?a[n] interesting, if it meets m constraints. The i-th of the m constraints consists of three integers li, ri, qi (1?≤?li?≤?ri?≤?n) meaning that value  should be equal to qi.

Your task is to find any interesting array of n elements or state that such array doesn't exist.

Expression x&y means the bitwise AND of numbers x and y. In programming languages C , Java and Python this operation is represented as "&", in Pascal ? as "and".

Input

The first line contains two integers n, m (1?≤?n?≤?105, 1?≤?m?≤?105) ? the number of elements in the array and the number of limits.

Each of the next m lines contains three integers li, ri, qi (1?≤?li?≤?ri?≤?n, 0?≤?qi?

Output

If the interesting array exists, in the first line print "YES" (without the quotes) and in the second line print n integers a[1],?a[2],?...,?a[n](0?≤?a[i]?

If the interesting array doesn't exist, print "NO" (without the quotes) in the single line.

Sample test(s)

input

3 11 3 3

output

YES3 3 3

input

3 21 3 31 3 2

output

NO

题意：给出很多个区间，使得每个区间的值相与为qi，要求构造出n个数使得每个区间都满足

思路：比如第i个区间，如果里面所有的数相与要为qi，那么将这些数写成二进制以后qi为1的位要全为1，剩下的位至少有一个要为0

            那么我可以初始化n个数为0，先把所有位必须为1的构造出来，对于m个区间可以用线段树完成，只做懒操作，区间的值相或（先不向上更新）

            然后再从1到n扫一遍线段树，把每个位置的数都更新到位，然后再次对于m个区间，现在只做向上更新（区间的值相与），然后只要所有区间的值都等于qi就能够成功构

            造出来