Cho một mảng \(a\) có \(n\) phần tử, nhưng bạn chỉ được biết số \(n\) và \(q\) ràng buộc, mỗi ràng buộc có dạng i j k, nghĩa là \(a_i|a_j=k\) (| là phép toán bit OR). Bạn phải tìm mảng \(a\) có thứ tự từ điển nhỏ nhất thoả mãn cả \(q\) truy vấn.

Một mảng \(a\) được định nghĩa là nhỏ hơn một mảng \(b\) theo thứ tự từ điển khi và chỉ khi ở vị trí đầu tiên mà \(a[i]\) khác \(b[i]\) thì \(a[i] < b[i]\).

Input

Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(q\).

\(q\) dòng tiếp theo mỗi dòng là một bộ ba số \(i\) \(j\) \(k\), mô tả cho mỗi ràng buộc.

Dữ liệu đầu vào đảm bảo tồn tại ít nhất một mảng \(a\) thoả mãn \(q\) truy vấn.

Output

Một dòng gồm \(n\) số nguyên là mảng \(a\).

Constraints

• \(n \le 10^5\)
• \(q \le 2*10^5\)
• \(i, j \le n\)
• \(k \le 2^{30}\)

Example

4 3
1 2 3
1 3 2
4 1 2

0 3 2 2 

0 3 2 2
2 1 0 0
2 1 2 0
2 1 2 2
2 3 0 0
2 3 0 2
2 3 2 0
2 3 2 2

1 0

0

2 1
1 1 1073741823

1073741823 0