题目描述

体育老师让 $N$ 个同学站成一排。老师有一个奇怪的癖好：他希望所有身穿奇数编号球衣的同学排在前面，身穿偶数编号球衣的同学排在后面。 同时，在奇数队和偶数队内部，都要按照球衣编号从小到大排序。 请你帮助体育老师排好这个队列。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 1000$)。 第二行包含 $N$ 个正整数 $a_i$ ($1 \le a_i \le 10000$)，表示同学们的球衣编号。

输出格式

输出一行，包含 $N$ 个整数，表示排好序后的队列。

样例

10
1 2 3 4 5 6 7 8 9 10

1 3 5 7 9 2 4 6 8 10