[建图]2+ doors Codeforces1715D

The Narrator has an integer array 𝑎a of length 𝑛n, but he will only tell you the size 𝑛n and 𝑞q statements, each of them being three integers 𝑖,𝑗,𝑥i,j,x, which means that 𝑎𝑖∣𝑎𝑗=𝑥ai∣aj=x, where || denotes the bitwise OR operation.

Find the lexicographically smallest array 𝑎a that satisfies all the statements.

An array 𝑎a is lexicographically smaller than an array 𝑏b of the same length if and only if the following holds: 

• in the first position where 𝑎a and 𝑏b differ, the array 𝑎a has a smaller element than the corresponding element in 𝑏b. 

Input

In the first line you are given with two integers 𝑛n and 𝑞q (1≤𝑛≤1051≤n≤105, 0≤𝑞≤2⋅1050≤q≤2⋅105).

In the next 𝑞q lines you are given with three integers 𝑖i, 𝑗j, and 𝑥x (1≤𝑖,𝑗≤𝑛1≤i,j≤n, 0≤𝑥<2300≤x<230) — the statements.

It is guaranteed that all 𝑞q statements hold for at least one array.

Output

On a single line print 𝑛n integers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (0≤𝑎𝑖<2300≤ai<230) — array 𝑎a.

Examples

input

4 3
1 2 3
1 3 2
4 1 2

output

0 3 2 2 

input

1 0

output

0 

input

2 1
1 1 1073741823

output

1073741823 0 

题意： 给出q个条件，需要你构造出满足这些条件的字典序最小的长度为n的数组。每个条件由i j x构成，表示第i个数按位或第j个数结果为x。

分析： 类似第46届icpc沈阳站的一道题目，也是将30位分开单独来看，建30张图。首先对于连边为0的两点，它们的取值必然都是0，之后对于连边为1且一个点赋值为0另一个点尚未赋值的情况，那个没赋值的一定会取1，之后就剩下最后一种情况了，连边为1且两点都未赋值，这种情况下可以对这些边排序，先保证边(u, v)中u < v，然后按照first升序，相同时按照second升序，然后按照顺序扫描一遍这些边，先看first，如果first还未赋值，那second要么也未赋值要么被赋为1，此时按照字典序最小的思想贪心，应该让first取0，second取1，如果first已经被赋值了，要是first是0，那么second无论如何都得是1了，要是first是1，那其实second是多少都无所谓，此时并不能确定second取什么值，有可能取了0或1后会影响到后面的贪心选值，所以现在先不给second赋值，当遍历完这些边后还未赋值的点直接取0即可。对于每位都进行这样的处理，就能求出这n个数在这一位上取值是多少了。

具体代码如下：

#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
#define pii pair
using namespace std;
 
struct node{
	int u, v, w;
}g[200005][35];
 
int ans[200005], num[200005];
vector e;
 
signed main()
{
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= q; i++){
		int u, v, x;
		scanf("%lld%lld%lld", &u, &v, &x);
		for(int j = 0; j < 30; j++){
			g[i][j] = {u, v, x&1};
			x >>= 1;
		}
	}
	for(int i = 0; i < 30; i++){
		e.clear();
		for(int j = 1; j <= n; j++) num[j] = -1;
		for(int j = 1; j <= q; j++){
			int u, v, w;
			u = g[j][i].u;
			v = g[j][i].v;
			w = g[j][i].w;
			if(w == 0){
				num[u] = 0;
				num[v] = 0;
			}
		}
		for(int j = 1; j <= q; j++){
			int u, v, w;
			u = g[j][i].u;
			v = g[j][i].v;
			w = g[j][i].w;
			if(w == 1 && num[u] == 0 && num[v] == -1)
				num[v] = 1;
			if(w == 1 && num[v] == 0 && num[u] == -1)
				num[u] = 1;
		}
		for(int j = 1; j <= q; j++){
			int u, v, w;
			u = g[j][i].u;
			v = g[j][i].v;
			w = g[j][i].w;
			if(w == 1){
				if(u > v) swap(u, v);
				e.push_back(make_pair(u, v));
			}
		}
		sort(e.begin(), e.end());
		for(int j = 0; j < e.size(); j++){
			if(num[e[j].first] == -1){
				num[e[j].first] = 0;
				num[e[j].second] = 1;
			}
			else if(num[e[j].first] == 0){
				num[e[j].second] = 1;
			}
		}
		for(int j = 1; j <= n; j++)
			if(num[j] != -1) ans[j] |= (num[j]<
	}
	for(int i = 1; i <= n; i++)
		printf("%lld ", ans[i]);
	return 0;
}