#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>
#include <ctime>
#include <list>
#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int f(int a, int b){
	return a || !b;
}

bool check(vector<int> v){
	if (v.empty()) return true;
	for (int i = v.size() - 2; i >= 0; --i){
		v[i] = f(v[i], v[i + 1]);
	}
	return v[0];
}

double calc(vector<int> v){
	double res = 1;
	reverse(ALL(v));
	rep(i, v.size()){
		res = pow(v[i], res);
	}
	return res;
}

vector<int> naive(vector<int> v){
	sort(ALL(v));
	double Max = -1;
	vector<int> res = vector<int>(REV(v));
	do{
		double x = calc(v);
		if (Max < x || abs(Max - x) < 1e-8 && v < res){
			Max = x, res = v;
		}
	} while (next_permutation(ALL(v)));
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a, b;
	rep(i, n){
		int x;
		cin >> x;
		if (x < 2) a.push_back(x);
		else b.push_back(x);
	}
	sort(ALL(a));
	rep(i, a.size()){
		if (a[i] && i % 2){
			swap(a[i - 1], a[i]);
			break;
		}
	}
	sort(ALL(b));

	if (b.size() && !check(a)){
		int tmp = a.back();
		a.pop_back();
		a.push_back(b[0]);
		a.push_back(tmp);
		b.erase(b.begin());
	}

	int k = b.size();
	if (k > 1 && b[k - 1] == 3 && b[k - 2] == 2) swap(b[k - 1], b[k - 2]);

	for (auto x : a) b.push_back(x);

	rep(i, n) cout << b[i] << endl;

	//auto bb = naive(b);
	//rep(i, n) cout << bb[i] << endl;

	return 0;
}
### Prompt

Your challenge is to write 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 <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <climits>
#include <bitset>
#include <cassert>
#include <ctime>
#include <list>
#ifdef _MSC_VER
#include <agents.h>
#endif

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end())
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

int f(int a, int b){
	return a || !b;
}

bool check(vector<int> v){
	if (v.empty()) return true;
	for (int i = v.size() - 2; i >= 0; --i){
		v[i] = f(v[i], v[i + 1]);
	}
	return v[0];
}

double calc(vector<int> v){
	double res = 1;
	reverse(ALL(v));
	rep(i, v.size()){
		res = pow(v[i], res);
	}
	return res;
}

vector<int> naive(vector<int> v){
	sort(ALL(v));
	double Max = -1;
	vector<int> res = vector<int>(REV(v));
	do{
		double x = calc(v);
		if (Max < x || abs(Max - x) < 1e-8 && v < res){
			Max = x, res = v;
		}
	} while (next_permutation(ALL(v)));
	return res;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	int n;
	cin >> n;
	vector<int> a, b;
	rep(i, n){
		int x;
		cin >> x;
		if (x < 2) a.push_back(x);
		else b.push_back(x);
	}
	sort(ALL(a));
	rep(i, a.size()){
		if (a[i] && i % 2){
			swap(a[i - 1], a[i]);
			break;
		}
	}
	sort(ALL(b));

	if (b.size() && !check(a)){
		int tmp = a.back();
		a.pop_back();
		a.push_back(b[0]);
		a.push_back(tmp);
		b.erase(b.begin());
	}

	int k = b.size();
	if (k > 1 && b[k - 1] == 3 && b[k - 2] == 2) swap(b[k - 1], b[k - 2]);

	for (auto x : a) b.push_back(x);

	rep(i, n) cout << b[i] << endl;

	//auto bb = naive(b);
	//rep(i, n) cout << bb[i] << endl;

	return 0;
}
```