Визначаємо послідовності \(S_n\) наступним чином.

• \(S_1\) це послідовність довжиною 1, що містить одну 1.

• \(S_n\) (n — ціле число, більше або дорівнює 2) — послідовність, отримана конкатенацією \(S_{n-1}\), \(n\), \(S_{n-1}\) в такому порядку.

Наприклад, \(S_2\) та \(S_3\) визначається наступним чином.

• \(S_2\) є конкатенацією \(S_1\), 2 та \(S_1\), у такому порядку, тож це 1,2,1.

• \(S_3\) є конкатенацією \(S_2\), 3 та \(S_2\), у такому порядку, тож це 1,2,1,3,1,2,1.

Дано \(N\). Вивести всю послідовність \(S_N\).

Обмеження

• \(1 \leq N \leq 16\)

Формат вхідних даних

Вхідний потік містить ціле число \(N\)

Формат вихідних даних

У вихідний потік виведіть \(S_N\)

Приклад вхідних даних

2

Приклад вихідних даних

1 2 1

Приклад вхідних даних

1

Приклад вихідних даних

1

Приклад вхідних даних

4

Приклад вихідних даних

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1