#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vi a;
  int cnt1 = 0;
  int cnt0 = 0;
  for(int i=0;i<(n);++i) {
    int tmp; cin >> tmp;
    if(tmp == 0) cnt0++;
    else if(tmp == 1) cnt1++;
    else a.push_back(tmp);
  }
  sort(a.begin(), a.end());
  bool is2andone3 = true;
  int cnt3 = 0;
  int cnt2 = 0;
  for(int i=0;i<((int)(a.size()));++i) {
    cnt3 += a[i] == 3;
    cnt2 += a[i] == 2;
    is2andone3 &= a[i] == 2 || a[i] == 3;
  }
  is2andone3 &= cnt2 > 0 && cnt3 == 1;
  if(is2andone3) {
    swap(a[(int)(a.size())-2], a[(int)(a.size())-1]);
  }
  if(cnt0 + cnt1 == n) {
    if(cnt0 % 2 == 0) {
      for(int i=0;i<(cnt0);++i) cout << 0 << endl;
      for(int i=0;i<(cnt1);++i) cout << 1 << endl;
    } else if(cnt1 > 0) {
      for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
      cout << 1 << endl;
      cout << 0 << endl;
      for(int i=0;i<(cnt1-1);++i) cout << 1 << endl;
    } else {
      for(int i=0;i<(cnt0);++i) cout << 0 << endl;
    }
  } else if(cnt0 > 0) {
    if(cnt1 > 0) {
      if(cnt0 % 2 == 0) {
        for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0);++i) cout << 0 << endl;
        for(int i=0;i<(cnt1);++i) cout << 1 << endl;
      } else {
        for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
        cout << 1 << endl;
        cout << 0 << endl;
        for(int i=0;i<(cnt1-1);++i) cout << 1 << endl;
      }
    } else {
      if(cnt0 % 2 == 0) {
        for(int i=(0);i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0);++i) cout << 0 << endl;
      } else {
        if(is2andone3 && (int)(a.size()) == 2) {
          swap(a[(int)(a.size())-2], a[(int)(a.size())-1]);
        }
        for(int i=(1);i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
        cout << a[0] << endl;
        cout << 0 << endl;
      }
    }
  } else {
    for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
    for(int i=0;i<(cnt1);++i) cout << 1 << endl;
  }
}


### Prompt

Generate a CPP solution to the following problem:

Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to perform a very large number of calculations to improve the calculation power and raise awareness. Exponentiation is an operation that easily produces large numbers.

There are N non-negative integers A1, A2, ..., AN. We would like to find the sorts B1, B2, ..., BN that maximize B1B2 ... BN -1BN. Of course, it is common sense for rabbits, but this calculation is performed in order from the upper right. We also promise that 00 = 1.

There may be multiple types of B1, B2, ..., and BN that satisfy the maximum conditions. In such a case, let's choose the smallest column in the dictionary order.



Input


N
A1
...
AN


Satisfy 1 ≤ N ≤ 100, 0 ≤ Ai ≤ 1,000,000,000.

Output

The output consists of N lines. Output Bi on line i.

Examples

Input

4
7
5
10
6


Output

5
6
7
10


Input

3
0
0
1000000000


Output

1000000000
0
0

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
  if(a < b) {a = b; return true;}
  return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
  if(a > b) {a = b; return true;}
  return false;
}
template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}
template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for(int i=0;i<((int)(v.size()));++i) {
    if(i) os << " ";
    os << v[i];
  }
  return os;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vi a;
  int cnt1 = 0;
  int cnt0 = 0;
  for(int i=0;i<(n);++i) {
    int tmp; cin >> tmp;
    if(tmp == 0) cnt0++;
    else if(tmp == 1) cnt1++;
    else a.push_back(tmp);
  }
  sort(a.begin(), a.end());
  bool is2andone3 = true;
  int cnt3 = 0;
  int cnt2 = 0;
  for(int i=0;i<((int)(a.size()));++i) {
    cnt3 += a[i] == 3;
    cnt2 += a[i] == 2;
    is2andone3 &= a[i] == 2 || a[i] == 3;
  }
  is2andone3 &= cnt2 > 0 && cnt3 == 1;
  if(is2andone3) {
    swap(a[(int)(a.size())-2], a[(int)(a.size())-1]);
  }
  if(cnt0 + cnt1 == n) {
    if(cnt0 % 2 == 0) {
      for(int i=0;i<(cnt0);++i) cout << 0 << endl;
      for(int i=0;i<(cnt1);++i) cout << 1 << endl;
    } else if(cnt1 > 0) {
      for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
      cout << 1 << endl;
      cout << 0 << endl;
      for(int i=0;i<(cnt1-1);++i) cout << 1 << endl;
    } else {
      for(int i=0;i<(cnt0);++i) cout << 0 << endl;
    }
  } else if(cnt0 > 0) {
    if(cnt1 > 0) {
      if(cnt0 % 2 == 0) {
        for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0);++i) cout << 0 << endl;
        for(int i=0;i<(cnt1);++i) cout << 1 << endl;
      } else {
        for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
        cout << 1 << endl;
        cout << 0 << endl;
        for(int i=0;i<(cnt1-1);++i) cout << 1 << endl;
      }
    } else {
      if(cnt0 % 2 == 0) {
        for(int i=(0);i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0);++i) cout << 0 << endl;
      } else {
        if(is2andone3 && (int)(a.size()) == 2) {
          swap(a[(int)(a.size())-2], a[(int)(a.size())-1]);
        }
        for(int i=(1);i<((int)(a.size()));++i) cout << a[i] << endl;
        for(int i=0;i<(cnt0-1);++i) cout << 0 << endl;
        cout << a[0] << endl;
        cout << 0 << endl;
      }
    }
  } else {
    for(int i=0;i<((int)(a.size()));++i) cout << a[i] << endl;
    for(int i=0;i<(cnt1);++i) cout << 1 << endl;
  }
}


```