← 返回题目列表

Codeforces · 1174/B

B. Ehab 是个奇怪的人

中文机器翻译题面 查看原题

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。您可以根据需要多次对其执行以下操作:

- 选择两个整数 $$$i$$$ 和 $$$j$$$ $$$(1 \le i,j \le n)$$$ 使得 $$$a_i+a_j$$$ 为奇数,然后交换 $$$a_i$$$ 和 $$$a_j$$$。

按字典顺序,您可以获得的最小数组是多少?

如果存在索引 $$$i$$$,使得 $$$x_i<y_i$$$ 且 $$$x_j=y_j$$$ 对于所有 $$$1 \le j < i$$$,则数组 $$$x$$$ 按字典顺序小于数组 $$$y$$$。不太正式,在它们不同的第一个索引 $$$i$$$ 处,$$$x_i<y_i$$$

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

第二行包含 $$$n$$$ 以空格分隔的整数 $$$a_1$$$、$$$a_2$$$、$$$\ldots$$$、$$$a_{n}$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

输出

唯一的行包含 $$$n$$$ 空格分隔的整数,这是您可以获得的按字典顺序排列的最小数组。

示例

输入 #1

3
4 1 7

输出 #1

1 4 7

输入 #2

2
1 1

输出 #2

1 1

注意

在第一个例子中,我们可以交换 $$$1$$$ 和 $$$4$$$ 因为 $$$1+4=5$$$,这是奇怪的。