D. 2+ doors
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\).
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.
On a single line print \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i < 2^{30}\)) — array \(a\).
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]\).