#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>

using namespace std;

int in[1001];
string dp[101][101][2];

bool check(string &s){
  int cur=s[s.size()-1]-'0';
  for(int i=s.size()-2;i>=0;i--){
    if(s[i]=='0'&&cur==1)cur=0;
    else cur=1;
  }
  return cur==1;
}

string dfs(int zero,int one,int dig){
  if(!(zero|one))return "";
  if(dp[zero][one][dig]!="-1")
    return dp[zero][one][dig];
  if(one==0&&zero==1&&dig==0)return "0";
  if(one==1&&zero==0&&dig==1)return "1";
  string res;
  string tmp;
  if(zero>=1){
    if(dig==1){
      string a='0'+dfs(zero-1,one,0);
      if(dfs(zero-1,one,0)!="n"){
	if(res=="")res=a;
	else res=min(res,a);
      }
    }
    else{
      string a='0'+dfs(zero-1,one,1);
      if(dfs(zero-1,one,1)!="n"){
	if(res=="")res=a;
	else res=min(res,a);
      }
    }
  }
  if(one>=1){
    if(dig==1){
      for(int i=0;i<2;i++){
	string a='1'+dfs(zero,one-1,i);
	if(dfs(zero,one-1,i)!="n"){
	  if(res=="")res=a;
	  else res=min(res,a);
	}
      }
    }
  }
  if(res=="")res="n";
  return dp[zero][one][dig]=res;
}

int main(){
  int N;
  cin>>N;
  for(int i=0;i<N;i++)cin>>in[i];
  int one,zero;
  zero=one=0;
  int cnt=0;
  for(int i=0;i<N;i++){
    if(in[i]==0)zero++;
    else if(in[i]==1)one++;
    else in[cnt++]=in[i];
  }
  sort(in,in+cnt);
  if(one>=1||!(one|zero)){
    if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
      swap(in[cnt-1],in[cnt-2]);
    // 最後に1がつくれる場合
    // どの順番が辞書順最初になるか調べる
    for(int i=0;i<101;i++)
      for(int j=0;j<101;j++)
	for(int k=0;k<2;k++)
	  dp[i][j][k]="-1";
    string a=dfs(zero,one,1);
    for(int i=0;i<a.size();i++)
      in[cnt++]=a[i]-'0';
  }
  else{
    if(zero%2==1){
      int tmp=in[0];
      for(int i=0;i<cnt-1;i++)in[i]=in[i+1];
      in[cnt-1]=tmp;
      // 1が無いので、適当なやつをまぜて1をつくる
      for(int i=0;i<101;i++)
	for(int j=0;j<101;j++)
	  for(int k=0;k<2;k++)
	    dp[i][j][k]="-1";
      string a=dfs(zero,1,1);
      cnt--;
      if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
	swap(in[cnt-1],in[cnt-2]);
      for(int i=0;i<a.size();i++){
	if(a[i]-'0'==1)in[cnt++]=tmp;
	in[cnt++]=0;
      }
    }
    else{
      if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
	swap(in[cnt-1],in[cnt-2]);
      for(int i=0;i<zero;i++)in[cnt++]=0;
    }
  }
  
  for(int i=0;i<N;i++)
    cout<<in[i]<<endl;
  
  return 0;
}
### 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 <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>

using namespace std;

int in[1001];
string dp[101][101][2];

bool check(string &s){
  int cur=s[s.size()-1]-'0';
  for(int i=s.size()-2;i>=0;i--){
    if(s[i]=='0'&&cur==1)cur=0;
    else cur=1;
  }
  return cur==1;
}

string dfs(int zero,int one,int dig){
  if(!(zero|one))return "";
  if(dp[zero][one][dig]!="-1")
    return dp[zero][one][dig];
  if(one==0&&zero==1&&dig==0)return "0";
  if(one==1&&zero==0&&dig==1)return "1";
  string res;
  string tmp;
  if(zero>=1){
    if(dig==1){
      string a='0'+dfs(zero-1,one,0);
      if(dfs(zero-1,one,0)!="n"){
	if(res=="")res=a;
	else res=min(res,a);
      }
    }
    else{
      string a='0'+dfs(zero-1,one,1);
      if(dfs(zero-1,one,1)!="n"){
	if(res=="")res=a;
	else res=min(res,a);
      }
    }
  }
  if(one>=1){
    if(dig==1){
      for(int i=0;i<2;i++){
	string a='1'+dfs(zero,one-1,i);
	if(dfs(zero,one-1,i)!="n"){
	  if(res=="")res=a;
	  else res=min(res,a);
	}
      }
    }
  }
  if(res=="")res="n";
  return dp[zero][one][dig]=res;
}

int main(){
  int N;
  cin>>N;
  for(int i=0;i<N;i++)cin>>in[i];
  int one,zero;
  zero=one=0;
  int cnt=0;
  for(int i=0;i<N;i++){
    if(in[i]==0)zero++;
    else if(in[i]==1)one++;
    else in[cnt++]=in[i];
  }
  sort(in,in+cnt);
  if(one>=1||!(one|zero)){
    if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
      swap(in[cnt-1],in[cnt-2]);
    // 最後に1がつくれる場合
    // どの順番が辞書順最初になるか調べる
    for(int i=0;i<101;i++)
      for(int j=0;j<101;j++)
	for(int k=0;k<2;k++)
	  dp[i][j][k]="-1";
    string a=dfs(zero,one,1);
    for(int i=0;i<a.size();i++)
      in[cnt++]=a[i]-'0';
  }
  else{
    if(zero%2==1){
      int tmp=in[0];
      for(int i=0;i<cnt-1;i++)in[i]=in[i+1];
      in[cnt-1]=tmp;
      // 1が無いので、適当なやつをまぜて1をつくる
      for(int i=0;i<101;i++)
	for(int j=0;j<101;j++)
	  for(int k=0;k<2;k++)
	    dp[i][j][k]="-1";
      string a=dfs(zero,1,1);
      cnt--;
      if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
	swap(in[cnt-1],in[cnt-2]);
      for(int i=0;i<a.size();i++){
	if(a[i]-'0'==1)in[cnt++]=tmp;
	in[cnt++]=0;
      }
    }
    else{
      if(cnt!=1&&in[cnt-1]==3&&in[cnt-2]==2)
	swap(in[cnt-1],in[cnt-2]);
      for(int i=0;i<zero;i++)in[cnt++]=0;
    }
  }
  
  for(int i=0;i<N;i++)
    cout<<in[i]<<endl;
  
  return 0;
}
```