DWITE Online Computer Programming Contest, December 2009, Problem 2

There are a few different rounding methods. The most common one rounds up/down from 5. Another one rounds up/down depending on the number being even or odd (this has to do with statistical bias). Here we'll implement yet another type of rounding — rounding a number to the closest whole integer in the Fibonacci sequence. If two elements in the sequence are equally far away, round up.

The Fibonacci sequence is defined as:

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

Which produces a sequence of: $0,1,1,2,3,5,8,13,21,34,\dots$

The input will contain 5 lines, integers $0\le N\le 1000000000$.

The output will contain 5 lines, each a corresponding integer rounded to the closest number from the Fibonacci sequence.

Sample Input

1
2
4
22
1000000000

Sample Output

1
2
5
21
1134903170

Problem Resource: DWITE