[Solution] 2+ doors Codeforces Solution|Solution Codeforces

D. 2+ doors

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

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

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

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

Input

In the first line you are given with two integers n$n$ and q$q$ (1≤n≤105$1\le n\le {10}^5$, 0≤q≤2⋅105$0\le q\le 2\cdot {10}^5$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

In the next q$q$ lines you are given with three integers i$i$, j$j$, and x$x$ (1≤i,j≤n$1\le i,j\le n$, 0≤x<230$0\le x<2^{30}$) — the statements.

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

Output

On a single line print n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$ (0≤ai<230$0\le a_i<2^{30}$) — array a$a$.