Леше подарили новую игру «НОД-перестановки». Каждый раунд этой игры проходит следующим образом:
- Сначала Леша выбирает перестановку\(^{\dagger}\) \(a_1, a_2, \ldots, a_n\) целых чисел от \(1\) до \(n\).
- После этого для всех \(i\) от \(1\) до \(n\) вычисляется целое число \(d_i = \gcd(a_i, a_{(i \bmod n) + 1})\).
- Счёт раунда равен количеству различных чисел среди \(d_1, d_2, \ldots, d_n\).
Лёша уже сыграл несколько раундов и ему захотелось найти такую перестановку \(a_1, a_2, \ldots, a_n\), что его счёт будет максимально возможным.
Напомним, что \(\gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\), а \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).
\(^{\dagger}\)Перестановкой длины \(n\) является массив, состоящий из \(n\) различных целых чисел от \(1\) до \(n\) в произвольном порядке. Например, \([2,3,1,5,4]\) — перестановка, но \([1,2,2]\) не перестановка (\(2\) встречается в массиве дважды) и \([1,3,4]\) тоже не перестановка (\(n=3\), но в массиве встречается \(4\)).
Выходные данные
Для каждого набора входных данных выведите \(n\) различных целых чисел \(a_{1},a_{2},\ldots,a_{n}\) (\(1 \le a_i \le n\)) — искомую перестановку.
Если существует несколько перестановок, на которых достигается максимальный счёт, вы можете вывести любую.
Примечание
В первом наборе входных данных Леше надо найти перестановку чисел от \(1\) до \(5\). Для перестановки \(a=[1,2,4,3,5]\) массив \(d\) равен \([1,2,1,1,1]\). Он содержит \(2\) различных числа, что является максимумом среди всех перестановок из \(5\) чисел. Существуют и другие ответы для этого набора входных данных.
Во втором наборе входных данных Леше надо найти перестановку чисел от \(1\) до \(2\). Всего существует две такие перестановки — \(a=[1,2]\) и \(a=[2,1]\). В обоих случаях массив \(d\) равен \([1,1]\), поэтому обе перестановки являются корректным ответом.
В третьем наборе входных данных Леше надо найти перестановку чисел от \(1\) до \(7\). Для перестановки \(a=[1,2,3,6,4,5,7]\) массив \(d\) равен \([1,1,3,2,1,1,1]\). Он содержит \(3\) различных числа, а значит и счёт раунда с такой перестановкой равен \(3\). Можно показать, что не существует перестановки чисел от \(1\) до \(7\), счёт которой будет больше \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
5
2
7
10
|
1 2 4 3 5
1 2
1 2 3 6 4 5 7
1 2 3 4 8 5 10 6 9 7
|