В 179-й школе наконец решили построить крышу над полем для игры в футбол. Уже известно, что для строительства потребуется последовательно поставить \(n\) вертикальных опор. При этом директор школы хочет, чтобы высоты всех опор образовывали перестановку \(p\) чисел от \(0\) до \(n - 1\), где \(p_i\) — высота \(i\)-й слева опоры \((1 \le i \le n)\).
Вам, как заведующему строительством, известно, что стоимость постройки последовательности опор определяется как максимальное значение побитового исключающего ИЛИ высот всех пар соседних опор. Иными словами, стоимость постройки равна \(\max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}\), где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.
Найдите любую последовательность из высот опор \(p\) длины \(n\), стоимость постройки которой минимальна.
Здесь перестановкой является массив, состоящий из \(n\) различных целых чисел от \(0\) до \(n - 1\) в произвольном порядке. Например, \([2,3,1,0,4]\) — перестановка, но \([1,0,1]\) не перестановка (\(1\) встречается в массиве дважды) и \([1,0,3]\) тоже не перестановка (\(n=3\), но в массиве встречается \(3\)).
Выходные данные
Для каждого набора входных данных выведите \(n\) чисел \(p_1\), \(p_2\), \(\ldots\), \(p_n\) — последовательность из высот опор, стоимость постройки которой минимальна.
Если существует несколько решений, выведите любое из них.
Примечание
Для \(n = 2\) есть \(2\) возможные последовательности высот опор:
- \([0, 1]\) — цена постройки равна \(0 \oplus 1 = 1\).
- \([1, 0]\) — цена постройки равна \(1 \oplus 0 = 1\).
Для \(n = 3\) есть \(6\) возможных последовательностей высот опор:
- \([0, 1, 2]\) — цена постройки равна \(\max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3\).
- \([0, 2, 1]\) — цена постройки равна \(\max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3\).
- \([1, 0, 2]\) — цена постройки равна \(\max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2\).
- \([1, 2, 0]\) — цена постройки равна \(\max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3\).
- \([2, 0, 1]\) — цена постройки равна \(\max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2\).
- \([2, 1, 0]\) — цена постройки равна \(\max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3\).