D. 2+ стула
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У куратора из Омеги есть массив целых чисел $$$a$$$ длины $$$n$$$, и он может сказать вам только число $$$n$$$ и $$$q$$$ утверждений про массив, каждое из которых записывается как $$$i, j, x$$$, что означает, что $$$a_i \mid a_j = x$$$, где $$$|$$$ обозначает операцию побитового ИЛИ.

Найдите массив $$$a$$$, если про него также известно, что он лексикографически минимален среди всех массивов, которые удовлетворяют условиям.

Массив $$$a$$$ лексикографически меньше массива $$$b$$$ такой же длины, если и только если выполняется следующее:

  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в массиве $$$a$$$ элемент меньше, чем соответствующий элемент в $$$b$$$.
Входные данные

В первой строке вводятся два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$).

В каждой из следующих $$$q$$$ строк содержится три целых числа $$$i$$$, $$$j$$$ и $$$x$$$ ($$$1 \le i, j \le n$$$, $$$0 \le x < 2^{30}$$$) — утверждения про массив.

Гарантируется, что всегда существует такой массив, для которого выполняются все $$$q$$$ условий.

Выходные данные

На одной строке выведите $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — массив $$$a$$$.

Примеры
Входные данные
4 3
1 2 3
1 3 2
4 1 2
Выходные данные
0 3 2 2
Входные данные
1 0
Выходные данные
0
Входные данные
2 1
1 1 1073741823
Выходные данные
1073741823 0
Примечание

В первом примере под условия подходят следующие массивы:

  • $$$[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]$$$.