[Solution] 2+ doors solution codeforces

Table of Contents

2+ doors solution codeforces

2+ doors solution codeforces – 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.

[Solution] 2+ doors solution codeforces

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

In the next 𝑞q lines you are given with three integers 𝑖i𝑗j, and 𝑥x (1𝑖,𝑗𝑛1≤i,j≤n0𝑥<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

Copy
4 3
1 2 3
1 3 2
4 1 2
output

Copy
0 3 2 2
input

Copy
1 0
output

Copy
0

[Solution] 2+ doors solution codeforces

input

Copy
2 1
1 1 1073741823
output

Copy
1073741823 0
Note

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

  • [0,3,2,2][0,3,2,2],
  • [2,1,0,0][2,1,0,0],
  • [2,1,0,2][2,1,0,2],
  • [2,1,2,0][2,1,2,0],
  • [2,1,2,2][2,1,2,2],
  • [2,3,0,0][2,3,0,0],
  • [2,3,0,2][2,3,0,2],
  • [2,3,2,0][2,3,2,0],
  • [2,3,2,2][2,3,2,2].

 

For Solution

“Click Here”

Leave a Comment