1174B Ehab Is an Odd Person

妖狐艹你老母 2022-01-21 22:41 123阅读 0赞

B. Ehab Is an Odd Person

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You're given an array aa of length nn. You can perform the following operation on it as many times as you want:

*  Pick two integers ii and jj (1≤i,j≤n)(1≤i,j≤n) such that ai+ajai+aj is odd, then swap aiai and ajaj.

What is lexicographically the smallest array you can obtain?

An array xx is [lexicographically smaller][] than an array yy if there exists an index ii such that xi<yixi<yi, and xj=yjxj=yj for all 1≤j<i1≤j<i. Less formally, at the first index ii in which they differ, xi<yixi<yi

Input

The first line contains an integer nn (1≤n≤1051≤n≤105) — the number of elements in the array aa.

The second line contains nn space-separated integers a1a1, a2a2, ……, anan (1≤ai≤1091≤ai≤109) — the elements of the array aa.

Output

The only line contains nn space-separated integers, the lexicographically smallest array you can obtain.

Examples

input

Copy

3
    4 1 7

output

Copy

1 4 7

input

Copy

2
    1 1

output

Copy

1 1

Note

In the first example, we can swap 11 and 44 since 1+4=51+4=5, which is odd.

**题意：给了n个数，如果里面两个数的和是奇数，就能交换他们的位置，能无限次交换不同这种数，输出经过交换后字典序最小的排列，也就是从小到大的顺序。**

**题解:如果这些数里面有一个奇数和一个偶数，就能直接排序（也就是经过多次交换达到排序的效果），没有的话就原样输出。**

**c++：**

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,a[100010],odd=0,even=0;
        cin>>n;
        for(int i=0;i<n;i++)
        {
             cin>>a[i];
             if(a[i]&1) odd=1;
             else even=1;
        }
        if(odd&&even)
            sort(a,a+n);
        for(int i=0;i<n;i++)
            cout<<a[i]<<" ";
        return 0;
    }

python：

n=int(input())
    a=list(map(int,input().split()))
    odd=0;even=0
    for i in a:
              if i%2: odd=1
              else:even=1
    if odd and even:
              print(*sorted(a))
    else:print(*a)

[lexicographically smaller]: https://en.wikipedia.org/wiki/Lexicographical_order