2+ doors
Contest: Codeforces Round 816 (Div. 2)
Difficulty rating: 1900
Tags: 2-sat, bitmasks, graphs, greedy

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 $$$a_i \mid a_j = 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 format:
In the first line you are given with two integers $$$n$$$ and $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

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

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

Output format:
On a single line print $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — array $$$a$$$.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first sample, these are all the arrays satisfying the statements:

- $$$[0, 3, 2, 2]$$$,
- $$$[2, 1, 0, 0]$$$,
- $$$[2, 1, 0, 2]$$$,
- $$$[2, 1, 2, 0]$$$,
- $$$[2, 1, 2, 2]$$$,
- $$$[2, 3, 0, 0]$$$,
- $$$[2, 3, 0, 2]$$$,
- $$$[2, 3, 2, 0]$$$,
- $$$[2, 3, 2, 2]$$$.

Example input:
4 3
1 2 3
1 3 2
4 1 2

Example output:
0 3 2 2

Example input:
1 0

Example output:
0

Editorial:
The first observation is that we can solve the task separately bit by bit, because of
• bitwise or operation is "bit-independent": bits of one particular power don't affect other bits
• to gen a lexicographically minimal solution, we can combine solutions for each bit separately
This makes it possible for us to create a solution for a boolean array, and then run it $$$30$$$ times for all numbers and statements, considering only $$$i$$$-th bit in each run.
For ease of understanding let's speak in a language of graphs: we have an undirected graph with $$$n$$$ vertices, on each vertex, there is either $$$0$$$ or $$$1$$$, and on each edge, there is a bitwise or of numbers, that are written on vertices connected by that edge. We have to recover the numbers on the vertices after they were somehow lost, knowing, that numbers on the vertices create a lexicographically minimal sequence possible.
Initially, let's write $$$1$$$ on each of the vertices. Then walk through them and consider incidental edges. If any of the edges contain $$$0$$$, we must also write $$$0$$$ on our current vertex and the neighbor by that edge. After zeroing all the required vertices, let's try to make our sequence lexicographically minimal. Walk through the vertices again and try to write $$$0$$$ on each: to check if everything is ok, iterate over the incidental edges again. If any of them contains $$$1$$$ and connects us with a vertex with $$$0$$$, then we cannot make our vertex $$$0$$$.
Such solution works in $$$\mathcal{O}(\log(\max(a_i)) \cdot (n + m))$$$ time.
For a better understanding and more details, we suggest you look over the authors' solutions.