We're giving away nice huge bags containing number tiles! A bag we want to present to you contains n tiles. Each of them has a single number written on it — either 1 or 2.

However, there is one condition you must fulfill in order to receive the prize. You will need to put all the tiles from the bag in a sequence, in any order you wish. We will then compute the sums of all prefixes in the sequence, and then count how many of these sums are prime numbers. If you want to keep the prize, you will need to maximize the number of primes you get.

Can you win the prize? Hurry up, the bags are waiting!

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of number tiles in the bag. The following line contains n space-separated integers a_1, a_2, ..., a_n (a_i ∈ \{1, 2\}) — the values written on the tiles.

Output

Output a permutation b_1, b_2, ..., b_n of the input sequence (a_1, a_2, ..., a_n) maximizing the number of the prefix sums being prime numbers. If there are multiple optimal permutations, output any.

Examples

Input


5
1 2 1 2 1


Output


1 1 1 2 2


Input


9
1 1 2 1 1 1 2 1 1


Output


1 1 1 2 1 1 1 2 1

Note

The first solution produces the prefix sums 1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, \mathbf{\color{blue}{7}} (four primes constructed), while the prefix sums in the second solution are 1, \mathbf{\color{blue}{2}}, \mathbf{\color{blue}{3}}, \mathbf{\color{blue}{5}}, 6, \mathbf{\color{blue}{7}}, 8, 10, \mathbf{\color{blue}{11}} (five primes). Primes are marked bold and blue. In each of these cases, the number of produced primes is maximum possible.
//package code;
import java.io.*;
import java.util.*;
import java.util.Map.Entry;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.awt.Point;
/**
 *
 * @author prabhat // use stringbuilder,TreeSet, priorityQueue, x+y=(x&y + x|y);
 */                                                           //X+y=2*(x&y)+ x^y;
  public class  a
   {
   public static int n,max1=2000005,k,m,q,a[],a1[],mat[][],id,depth[],parent[][],len=22,tin[],tout[],count=0,size[],sum,cnt;
   public static Point[] p1,p2,p;
   public static long mod=(long)1e9+7,nCr[][],suf[][],ans=0,max=Long.MIN_VALUE,dp[],l,r;
   public static boolean isPrime[],visit[][],valid[][];
   public static HashSet<Integer> hash;
   public static PriorityQueue<Integer> pq[];
   public static  ArrayList<Integer> divisor[],prime,adj[],lpf,list[],pri;
   //public static ArrayList<Character> list[];
   public static  TreeMap<Integer,Integer> tmap[];
   public static String s;
   //public static pair[] pa;
   public  static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static PrintWriter pw;
   static int[] x={-1,0,1},y={1,0,-1};

   public static void main(String[] args) throws IOException
   {
	InputReader in = new InputReader(System.in);
	pw=new PrintWriter(System.out);
	n=in.ii();
	a=in.iia(n);
	int cnt1=0;
	int cnt2=0;
	for(int i:a)if(i==1)cnt1++; else cnt2++;
	if(cnt2>=1)pw.print(2+" "); cnt2--;
    if(cnt1>=1)pw.print(1+" ");cnt1--;
    for(int i=0;i<cnt2;i++)pw.print(2+" ");
    for(int i=0;i<cnt1;i++)pw.print(1+" ");
    pw.println();
	pw.close();
   }
  static boolean va(int x,int y,boolean[][] m)
  {
  	return x>=0&&x<n&&y>=0&&y<n&&!m[x][y];
  }
  static int gcd1(int x,int y)
  {
    if(x==0)return y;
    else if(y==0)return x;
    else return gcd(y,x%y);	 
  }
 
 static class pair1{
	 int node;
	 int time;
	 pair1(int s,int v)
	 {
	 	node=s;
	 	time=v;
	 }
 }  
static int lowerBound(ArrayList<Integer> al,int tar)
{
	   int s=0;
	   int e=al.size()-1;
	   int ans=0;
	   while(s<=e)
	   {
		   int mid=(s+e)/2;
		   if(al.get(mid)<=tar){s=mid+1;ans=mid+1;}
		   else e=mid-1;
	   }
	   return ans;
}

static boolean isVowel(char c)
{
	return c=='a'||c=='e'||c=='i'||c=='o'||c=='u';
}

public  static class DSU
{
	int[] parent;
	int[] rank;
	
	int cnt;
	public DSU(int n){
		parent=new int[n];
		rank=new int[n];
		for(int i=0;i<n;i++){
			parent[i]=i;
			rank[i]=1;
		}
		cnt=n;
	}
	int find(int i){
		while(parent[i] !=i){
			parent[i]=parent[parent[i]];
			i=parent[i];
		}
		return i;
	}
	void Union(int x, int y){
		int xset = find(x);
		int yset = find(y);
		if(xset!=yset)
			cnt--;
		
		if(rank[xset]>rank[yset])
		{
			parent[yset] = xset;
		    rank[xset]+=rank[yset];
			rank[yset]=0;
			//return xset;
		}else{
			parent[xset]=yset;
			rank[yset]+=rank[xset];
			rank[xset]=0;
			//return yset;
		}
	
     return;
	}
}


 static int palin(String s)
 {
	String s1=new StringBuilder(s).reverse().toString();
	return s1.equals(s)==true?1:0;
 }
 /*static int dfs(int u, int p) {

	//discover[count1++]=arr[u];  //  it storing color or arr of vertex u
	//discover[count1++]=u;
	//tin[u] = count++;
   int d1=1000000;
   int d2=1000000;
   int cnt=0;
	//parent[u][0] = p==-1?0:p;
	//size[u]++;
	//for (int i = 1; i < len; i++)
	//	parent[u][i] = parent[parent[u][i-1]][i-1];
	for (int v :adj[u])
		if (v != p)
		{
			cnt++;
			depth[v] = depth[u] + 1;
			int y=dfs( v, u);
			if(y<d1)
			{
				d2=d1;
				d1=y;
			}
			else if(y<d2)
			{
				d2=y;
			}
	//		size[u] += size[v];
		}
	if(cnt==0)return 1;
	ans=Math.min(d1+d2,ans);
	return 1+Math.min(d1,d2);
//	if(adj[u].size()==1&&parent[u][0]!=0)last.add(u);
//	tout[u] = count-1;
}
*/

static boolean isParent(int parent, int child) {
	return tin[parent] <= tin[child] && tout[child] <= tout[parent];
}

static int lca(int a, int b) {
	if (isParent(a, b))
		return a;
	if (isParent(b, a))
		return b;
	for (int i = len - 1; i >= 0; i--)
		if (!isParent(parent[a][i], b))
			a = parent[a][i];
	return parent[a][0];
}
static boolean valid(int i,int j)
{
	return i>=0&&i<3&&j>=0&&j<3;
}
 
static int gcd(int a,int b)
{
	while(a!=0)
	{
		int temp=a;
		a=b%a;
		b=temp;
	}
	return b;
}
static void Seive()
{
	a1=new int[max1];
	isPrime=new boolean[max1];
	Arrays.fill(isPrime,true);
	prime=new ArrayList<>();
	divisor=new ArrayList[max1];
	for(int i=1;i<max1;i++)divisor[i]=new ArrayList<Integer>();
    isPrime[0]=isPrime[1]=false;
	for(int i=2;i<(max1);i++)
	{
         if(isPrime[i]){
			 divisor[i].add(i);
			 prime.add(i);
			 a1[i]=1;
			for(int j=2*i;j<max1;j+=i)
			{
				a1[j]++;
				isPrime[j]=false;
				divisor[j].add(i);
			}
		}
	}
}
public static long pow(long n,long p)
{
	 long  result = 1;
	  if(p==0)
	    return 1;

	while(p!=0)
	{
	    if(p%2==1)
	        result *= n;
	    
	    p >>=1;
	    n*=n;
	}
	return result;
}


static  class InputReader
{
   private InputStream stream;
   private byte[] buf = new byte[1024];

   private SpaceCharFilter filter;
    byte inbuffer[] = new byte[1024];
   int lenbuffer = 0, ptrbuffer = 0;
    final int M = (int) 1e9 + 7;
   int md=(int)(1e7+1);
    int[] SMP=new int[md];
   final double eps = 1e-6;
   final double pi = Math.PI;

	PrintWriter out;
   String check = "";
 InputStream   obj = check.isEmpty() ? System.in : new ByteArrayInputStream(check.getBytes());
   public InputReader(InputStream stream)
   {
       this.stream = stream;
   }

    int readByte() {
	        if (lenbuffer == -1) throw new InputMismatchException();
	        if (ptrbuffer >= lenbuffer) {
	            ptrbuffer = 0;
	            try {
	                lenbuffer = obj.read(inbuffer);
	            } catch (IOException e) {
	                throw new InputMismatchException();
	            }
	        }
	        if (lenbuffer <= 0) return -1;
	        return inbuffer[ptrbuffer++];
   }

   public  int read()
   {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       int sgn = 1;
       if (c == '-')
       {
           sgn = -1;
           c = read();
       }
       int res = 0;
       do
       {
           if (c < '0' || c > '9')
               throw new InputMismatchException();
           res *= 10;
           res += c - '0';
           c = read();
       } while (!isSpaceChar(c));
       return res * sgn;
   }

   String is() {
	        int b = skip();
	        StringBuilder sb = new StringBuilder();
	        while (!(isSpaceChar(b))) // when nextLine, (isSpaceChar(b) && b!=' ')
	        {
	            sb.appendCodePoint(b);
	            b = readByte();
	        }
	        return sb.toString();
   }
   public   int ii() {
	        int num = 0, b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }
 public   long il() {
	        long num = 0;
	        int b;
	        boolean minus = false;
	        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
	        if (b == '-') {
	            minus = true;
	            b = readByte();
	        }
	        while (true) {
	            if (b >= '0' && b <= '9') {
	                num = num * 10 + (b - '0');
	            } else {
	                return minus ? -num : num;
	            }
	            b = readByte();
	        }
   }

	    boolean isSpaceChar(int c) {
	        return (!(c >= 33 && c <= 126));
	       }

	      int skip()
	        {
	        int b;
	        while ((b = readByte()) != -1 && isSpaceChar(b)) ;
	        return b;
	        }

	    float nf() {
	        return Float.parseFloat(is());
	    }

	    double id() {
	        return Double.parseDouble(is());
	    }

	    char ic() {
	        return (char) skip();
	    }

	    int[] iia(int n) {
	        int a[] = new int[n];
	        for (int i = 0; i<n; i++) a[i] = ii();
	        return a;
	    }

	    long[] ila(int n) {
	        long a[] = new long[n];
	        for (int i = 0; i <n; i++) a[i] = il();
	        return a;
	    }

	    String[] isa(int n) {
	        String a[] = new String[n];
	        for (int i = 0; i < n; i++) a[i] = is();
	        return a;
	    }


		 long mul(long a, long b) { return a * b % M; }

		/*	long div(long a, long b)
				 {
					return mul(a, pow(b, M - 2,M));

		           }
*/


	    double[][] idm(int n, int m) {
	        double a[][] = new double[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) a[i][j] = id();
	        return a;
	        }

	    int[][] iim(int n, int m) {
	        int a[][] = new int[n][m];
	        for (int i = 0; i < n; i++) for (int j = 0; j <m; j++) a[i][j] = ii();
	        return a;
          }


   public String readLine() {
       int c = read();
       while (isSpaceChar(c))
           c = read();
       StringBuilder res = new StringBuilder();
       do {
           res.appendCodePoint(c);
           c = read();
       } while (!isEndOfLine(c));
       return res.toString();
   }

   public interface SpaceCharFilter
   {
       public boolean isSpaceChar(int ch);
   }
   public boolean isEndOfLine(int c) {
       return c == '\n' || c == '\r' || c == -1;
   }
}

}
