#include <bits/stdc++.h>
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &a : v) is >> a;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const T &t : v) os << t << " ";
  return os << endl;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &v) {
  return os << v.first << " " << v.second;
}
double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }
vector<long long int> parent, rak;
void make_set(long long int f) {
  for (long long i = 0; i < f + 1; i++) parent.push_back(i);
  rak.assign(f + 1, 1);
}
long long int find_set(long long int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
long long int union_sets(long long int a, long long int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rak[a] < rak[b]) swap(a, b);
    parent[b] = a;
    rak[a] += rak[b];
    return (rak[a] - rak[b]) * (rak[b]);
  }
  return 0;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int extend_gcd(long long int a, long long int b, long long int &x,
                         long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int x1, y1;
  long long int ans = extend_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return ans;
}
long long int inverse(long long int a, long long int m) {
  long long int x, y;
  extend_gcd(m, a, x, y);
  y %= m;
  y += m;
  y %= m;
  return y;
}
unsigned long long fhash(vector<long long int> p, long long int len) {
  unsigned long long h = 0xcbf29ce484222325ULL;
  for (long long int i = 0; i < len; i++) h = (h ^ p[i]) * 0x100000001b3ULL;
  return h;
}
long long int kv;
long long int t, n, x, y, h, k, z, p, q, w;
string s, s2;
long long int kv1 = 0;
stack<long long int> s1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  long long int a[n];
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] % 2)
      x++;
    else
      y++;
  }
  if (x != 0 && y != 0) sort(a, a + n);
  for (auto it : a) cout << it << " ";
  cout << endl;
  ;
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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

  * Pick two integers i and j (1 ≤ i,j ≤ n) such that a_i+a_j is odd, then swap a_i and a_j. 



What is lexicographically the smallest array you can obtain?

An array x is [lexicographically smaller](https://en.wikipedia.org/wiki/Lexicographical_order) than an array y if there exists an index i such that x_i<y_i, and x_j=y_j for all 1 ≤ j < i. Less formally, at the first index i in which they differ, x_i<y_i

Input

The first line contains an integer n (1 ≤ n ≤ 10^5) — the number of elements in the array a.

The second line contains n space-separated integers a_1, a_2, …, a_{n} (1 ≤ a_i ≤ 10^9) — the elements of the array a.

Output

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

Examples

Input


3
4 1 7


Output


1 4 7 

Input


2
1 1


Output


1 1 

Note

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

### Response

```cpp
#include <bits/stdc++.h>
unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
using namespace std;
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &a : v) is >> a;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (const T &t : v) os << t << " ";
  return os << endl;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &v) {
  return os << v.first << " " << v.second;
}
double gcd(double a, double b) { return a < 0.01 ? b : gcd(fmod(b, a), a); }
vector<long long int> parent, rak;
void make_set(long long int f) {
  for (long long i = 0; i < f + 1; i++) parent.push_back(i);
  rak.assign(f + 1, 1);
}
long long int find_set(long long int v) {
  if (v == parent[v]) return v;
  return parent[v] = find_set(parent[v]);
}
long long int union_sets(long long int a, long long int b) {
  a = find_set(a);
  b = find_set(b);
  if (a != b) {
    if (rak[a] < rak[b]) swap(a, b);
    parent[b] = a;
    rak[a] += rak[b];
    return (rak[a] - rak[b]) * (rak[b]);
  }
  return 0;
}
struct hash_pair {
  template <class T1, class T2>
  size_t operator()(const pair<T1, T2> &p) const {
    auto hash1 = hash<T1>{}(p.first);
    auto hash2 = hash<T2>{}(p.second);
    return hash1 ^ hash2;
  }
};
long long bpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
long long int extend_gcd(long long int a, long long int b, long long int &x,
                         long long int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long int x1, y1;
  long long int ans = extend_gcd(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return ans;
}
long long int inverse(long long int a, long long int m) {
  long long int x, y;
  extend_gcd(m, a, x, y);
  y %= m;
  y += m;
  y %= m;
  return y;
}
unsigned long long fhash(vector<long long int> p, long long int len) {
  unsigned long long h = 0xcbf29ce484222325ULL;
  for (long long int i = 0; i < len; i++) h = (h ^ p[i]) * 0x100000001b3ULL;
  return h;
}
long long int kv;
long long int t, n, x, y, h, k, z, p, q, w;
string s, s2;
long long int kv1 = 0;
stack<long long int> s1;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  long long int a[n];
  for (long long i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] % 2)
      x++;
    else
      y++;
  }
  if (x != 0 && y != 0) sort(a, a + n);
  for (auto it : a) cout << it << " ";
  cout << endl;
  ;
  return 0;
}

```