На день рождения Ивану подарили последовательность неотрицательных целых чисел \(a_1, a_2, \ldots, a_n\). Он сразу же заметил, что каждый элемент последовательности \(a_i\) удовлетворяет условию \(0 \leq a_i \leq 15\).
Иван — большой любитель теории графов, поэтому он решил превратить подаренную последовательность в неориентированный граф.
В его графе будет \(n\) вершин, а ребро между вершинами \(u\) и \(v\) будет присутствовать тогда и только тогда, когда двоичные записи чисел \(a_u\) и \(a_v\) отличаются ровно в одном бите (иначе говоря, \(a_u \oplus a_v = 2^k\) для какого-то целого \(k \geq 0\), где \(\oplus\) это операция Побитовое исключающее ИЛИ (XOR)).
Через пару дней случилось страшное — Иван забыл последовательность \(a\), у него остался только построенный граф!
Можете ли вы помочь ему, и восстановить любую такую последовательность \(a_1, a_2, \ldots, a_n\), что граф, построенный по тем же правилам, которыми пользовался Иван, совпадет с его графом?
Выходные данные
Выведите \(n\) целых чисел, разделенных пробелами, \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 15\)).
Выведенные числа должны удовлетворять условию: в графе Ивана ребро между вершинами \(u\) и \(v\) присутствует тогда и только тогда, когда \(a_u \oplus a_v = 2^k\) для какого-то целого \(k \geq 0\).
Гарантируется, что есть хотя бы одно решение. Если возможных решений несколько, вы можете вывести любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
1 2
2 3
3 4
4 1
|
0 1 0 1
|
|
2
|
3 0
|
0 0 0
|