Sea la secuencia ~S_n~ de la siguiente manera:

• ~S_1~ es una secuencia de longitud 1 que contiene un solo 1.
• ~S_n~ (~n~ es un entero mayor o igual a 2) es una secuencia obtenida concatenando ~S_{n-1}~, ~n~, ~S_{n-1}~ en este orden.

Por ejemplo, ~S_2~ y ~S_3~ se definen de la siguiente manera:

• ~S_2~ es una concatenación de ~S_1~, ~2~ y ~S_1~, en este orden, por lo que es ~1, 2, 1~.
• ~S_3~ es una concatenación de ~S_2~, ~3~ y ~S_2~, en este orden, por lo que es ~1,2,1,3,1,2,1~.

Dado ~N~, imprime la secuencia ~S_n~ completa .

Restricciones

• es un entero.
• ~1 \leq N \leq 16~.

Entrada

Lea desde la entrada el valor de ~N~.

Salida

Imprime ~S_n~, con espacios entre cada número.

Ejemplo #1 de Entrada

2

Ejemplo #1 de Salida

1 2 1

Ejemplo #2 de Entrada

1

Ejemplo #2 de Salida

1

Ejemplo #3 de Entrada

4

Ejemplo #3 de Salida

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

~S_4~ es una concatenación de ~S_3~, ~4~ y ~S_3~, en ese orden.