У куратора из Омеги есть массив целых чисел \(a\) длины \(n\), и он может сказать вам только число \(n\) и \(q\) утверждений про массив, каждое из которых записывается как \(i, j, x\), что означает, что \(a_i \mid a_j = x\), где \(|\) обозначает операцию побитового ИЛИ.
Найдите массив \(a\), если про него также известно, что он лексикографически минимален среди всех массивов, которые удовлетворяют условиям.
Массив \(a\) лексикографически меньше массива \(b\) такой же длины, если и только если выполняется следующее:
- в первой позиции, где \(a\) и \(b\) различны, в массиве \(a\) элемент меньше, чем соответствующий элемент в \(b\).
Выходные данные
На одной строке выведите \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i < 2^{30}\)) — массив \(a\).
Примечание
В первом примере под условия подходят следующие массивы:
- \([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]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
1 2 3
1 3 2
4 1 2
|
0 3 2 2
|
|
2
|
1 0
|
0
|
|
3
|
2 1
1 1 1073741823
|
1073741823 0
|