Description

N个数，奇偶混排，现要让奇数在前偶数在后，原奇位位次与偶位位次保持不变。例如，7,3,2,8,5,4重排后得到7,3,5,2,8,4。请帮忙完成重新排位。

Input

多组数据。每组数据第一行为整数N（0＜N≤50），后续跟有N个整数（数值<=100）。若N=999表示输入结束。

Output

重新排位后输出，每个数间隔一个空格，行末无多余空格，每组数据在一行中输出。

Sample

Input

6
7 3 2 8 5 4
7
1 2 3 4 5 6 7
9
2 5 23 65 8 6 87 4 3
999

Output

7 3 5 2 8 4
1 3 5 7 2 4 6
5 23 65 87 3 2 8 6 4

Hint

奇数或偶数可能为空。

Source: qn