Planning Poker, also called Scrum poker, is a consensus-based technique for estimating, mostly used to estimate effort or relative size of user stories in software development.
A typical Planning Poker Deck has cards showing the Fibonacci sequence including a zero: 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. other decks use similar progressions.
We have some tasks estimated with other complexities from 1 to 10000000.
We need to estimate the complexity of all tasks using the Fibonacci sequence used in Planning Poker. The rule is that the old complexity will change to the valid complexity more close. But if two complexities are in equal distances take the higher.

Input

The input consists of multiple test cases.
Each test case begins with a line containing an integer “N” (1 <= N <= 100000) the number of tasks. In the following line are the complexities of "N" tasks from "0" to "N-1" (1 <= task[i] <= 10000000).
The end of input is indicated by a line with one zero. This is not a part of any test cases.

Output

For each test case print the list of new complexities sorted in ascending order. Print a space character between two complexities.

Example

Input:
5
1 2 3 4 5
5
7 8 9 11 10
0

Output:
1 2 3 5 5
8 8 8 8 13