Print Fibonacci Sequence

Given a positive integer n, print the first n terms of the Fibonacci sequence. The Fibonacci sequence is defined by the recurrence relation:

$$F(n)=F(n-1)+F(n-2)$$

with the base cases $$F(0)=0$$ and $$F(1)=1$$. The sequence starts with 0 and 1. Your task is to output the sequence with each term printed on its own line.

inputFormat

The input consists of a single integer n (\(n \ge 1\)) provided via standard input.

outputFormat

Output the first n Fibonacci numbers, each on a separate line, via standard output.

## sample

5

0
1
1
2
3

</p>