Fibonacci sequence

One integer $n$ is given. Print $n$ first elements of the Fibonacci sequence:

• $f(1)=1$,

• $f(2)=1$,

• $f(k)=f(k-1)+f(k-2),k=3,4,...$

Input

One integer $n(2\le n\le 31)$.

Output

Print $n$ first elements of the Fibonacci sequence, each in a separate line.

Examples