La successió de Finonacci és una serie de nombres que es calculen de forma automàtica, per a cada iteració es mostra el resultat de sumar el nombre actual a l'anterior i es comença sempre sumant els valors \(0\) i \(1\); per tant, el primer número que es mostra és sempre un \(1\). Aquest procés es repeteix fins a l'infinit, per exemple, si s'han mostrat els els nombres \(1\) \(1\) \(2\) \(3\) \(5\) \(8\) \(13\), el nombre actual és \(13\) i l'anterior és \(8\); per tant, el proper nombre seria \(13 + 8\), és a dir, \(21\).

Has de fer un programa que, donat un nombre \(N\), mostri aquesta quantitat de números de la successió de Fibonacci.

Input Format

L'entrada consisteix en un únic nombre enter.

Constraints

• \(N > 0\)

Output Format

S'imprimirà aquesta quantitat de nombres de la successió de Fibonacci, a la mateixa línia i separats per un espai.

Test Case 1

Input

1

Output

1

Test Case 2

Input

2

Output

1 1

Test Case 3

Input

3

Output

1 1 2

Test Case 4

Input

4

Output

1 1 2 3

Test Case 5

Input

5

Output

1 1 2 3 5

Test Case 6

Input

25

Output

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025