Codeforces Round #275 (Div. 2) D 線段樹

連結：戳這裡

D. Interesting Array time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard 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 < 230) describing the i-th limit.

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] < 230) decribing the interesting array. If there are multiple answers, print any of them.

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

Examples

input

3 1

1 3 3

output

YES

3 3 3

input

3 2

1 3 3

1 3 2

output

NO

題意：

給出m個區間[l,r]所有數的&值為vi

問是否存在這樣的一個序列

思路：

區間[l,r]取&值要為一個固定的數vi。考慮區間與區間之間的交的值取&必須相等，那麼二進制上對應的位置必須都存在1。

是以區間與區間之間直接取或就行了。然後因為要線上段上快速更新和查詢。用線段樹處理吧。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#include<bitset>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
#define INF (1ll<<60)-1
#define Max 1e9
using namespace std;
ll a[600100],tr[600100],lazy[600100];
int n,m;
void build(int root,int l,int r){
    if(l==r){
        tr[root]=0;
        lazy[root]=0;
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
}
void pushdown(int root){
    if(lazy[root]){
        tr[root*2]|=lazy[root];
        tr[root*2+1]|=lazy[root];
        lazy[root*2]|=lazy[root];
        lazy[root*2+1]|=lazy[root];
        lazy[root]=0;
    }
}
void update(int root,int l,int r,int x,int y,ll v){
    if(l>=x && r<=y){
        tr[root]|=v;
        lazy[root]|=v;
        return ;
    }
    pushdown(root);
    int mid=(l+r)/2;
    if(y<=mid) update(root*2,l,mid,x,y,v);
    else if(x>mid) update(root*2+1,mid+1,r,x,y,v);
    else {
        update(root*2,l,mid,x,mid,v);
        update(root*2+1,mid+1,r,mid+1,y,v);
    }
}
ll query(int root,int l,int r,int x,int y){
    if(l>=x && r<=y){
        return tr[root];
    }
    pushdown(root);
    int mid=(l+r)/2;
    if(y<=mid) return query(root*2,l,mid,x,y);
    else if(x>mid) return query(root*2+1,mid+1,r,x,y);
    else return query(root*2,l,mid,x,mid) & query(root*2+1,mid+1,r,mid+1,y);
}
void solve(int root,int l,int r){
    if(l==r) {
        a[l]=tr[root];
        return ;
    }
    int mid=(l+r)/2;
    tr[root*2]|=tr[root];
    tr[root*2+1]|=tr[root];
    solve(root*2,l,mid);
    solve(root*2+1,mid+1,r);
}
int l[100100],r[100100];
ll v[100100];
int main(){
    scanf("%d%d",&n,&m);
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d%d%I64d",&l[i],&r[i],&v[i]);
        update(1,1,n,l[i],r[i],v[i]);
    }
    for(int i=1;i<=m;i++){
        if(query(1,1,n,l[i],r[i])!=v[i]){
            cout<<"NO"<<endl;
            return 0;
        }
    }
    solve(1,1,n);
    cout<<"YES"<<endl;
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
    return 0;
}
/*
3 2
2 3 3
1 1 1
*/