Problem: During the break, we decided to relax and play dominoes. Our box with Domino was empty, so we decided to borrow the teacher's dominoes.

The teacher responded instantly at our request. He put nm dominoes on the table as an n × 2m rectangle so that each of the n rows contained m dominoes arranged horizontally. Each half of each domino contained number (0 or 1).

We were taken aback, and the teacher smiled and said: "Consider some arrangement of dominoes in an n × 2m matrix. Let's count for each column of the matrix the sum of numbers in this column. Then among all such sums find the maximum one. Can you rearrange the dominoes in the matrix in such a way that the maximum sum will be minimum possible? Note that it is prohibited to change the orientation of the dominoes, they all need to stay horizontal, nevertheless dominoes are allowed to rotate by 180 degrees. As a reward I will give you all my dominoes".

We got even more taken aback. And while we are wondering what was going on, help us make an optimal matrix of dominoes.

Input

The first line contains integers n, m (1 ≤ n, m ≤ 103).

In the next lines there is a description of the teachers' matrix. Each of next n lines contains m dominoes. The description of one domino is two integers (0 or 1), written without a space — the digits on the left and right half of the domino.

Output

Print the resulting matrix of dominoes in the format: n lines, each of them contains m space-separated dominoes.

If there are multiple optimal solutions, print any of them.

Examples

Input

2 3
01 11 00
00 01 11


Output

11 11 10
00 00 01


Input

4 1
11
10
01
00


Output

11
10
01
00

Note

Consider the answer for the first sample. There, the maximum sum among all columns equals 1 (the number of columns is 6, and not 3). Obviously, this maximum can't be less than 1, then such matrix is optimal.

Note that the dominoes can be rotated by 180 degrees.

Solution (in JAVA):

Solution:

import java.io.*;    //PrintWriter
import java.math.*;  //BigInteger, BigDecimal
import java.util.*;  //StringTokenizer, ArrayList


public class R231_Div2_C //Name: Dominoes
{	
	FastReader in;
	PrintWriter out;
	
	public static void main(String[] args)  {
		new R231_Div2_C().run();
	}
	
	void run()
	{		
		in = new FastReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}
	
	void solve()
	{
		int n = in.nextInt();
		int m = in.nextInt();
		
		@SuppressWarnings("unused")
		int one0 = 0, one1 = 0, one2 = 0;
		String s;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				s = in.next();
				if (s.equals("00")) one0++;
				else if (s.equals("11")) one2++;
				else one1++;
			}

		String[][] st = new String[n][m];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (one2 > 0)
				{
					one2--;
					if (i%2 == 0)
						st[i][j] = "11";
					else
						st[i][m-1-j] = "11";
				}
				else if (one1 > 0)
				{
				   	if (i%2 == 0)
				   		st[i][j]="10";
				   	else
				   		st[i][m-1-j]="01";
				   	one1--;
				}
				else
					if (i%2 == 0)
						st[i][j] = "00";
					else
						st[i][m-1-j] = "00";					
			}
		}
		
		for (int i = 0; i < n; i++)	
		{
			for (int j = 0; j < m; j++)
			{
				if (j > 0) out.print(" ");			
				out.print(st[i][j]);
			}
			out.println();
		}
	}

	//-----------------------------------------------------
	void runWithFiles() {
		in = new FastReader(new File("input.txt"));
		try {
			out = new PrintWriter(new File("output.txt"));
		} 
		catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		solve();
		out.close();
	}
	
	class FastReader
	{
	    BufferedReader br;
	    StringTokenizer tokenizer;
	    
	    public FastReader(InputStream stream)
	    {
	        br = new BufferedReader(new InputStreamReader(stream));
	        tokenizer = null;
	    }
		public FastReader(File f) {
			try {
				br = new BufferedReader(new FileReader(f));
				tokenizer = null;
			}
			catch (FileNotFoundException e) {
				e.printStackTrace();
			}
		}
	    
	    private String next() {
	        while (tokenizer == null || !tokenizer.hasMoreTokens())
	            try {
	            	tokenizer = new StringTokenizer(br.readLine());
	            }
	            catch (IOException e) {
	                throw new RuntimeException(e);
	            }
	        return tokenizer.nextToken();
	    }
		public String nextLine() {
			try	{
				return br.readLine();
			}
			catch(Exception e) {
				throw(new RuntimeException());
			}
		}

	    int nextInt() {
	        return Integer.parseInt(next());
	    }
	    long nextLong() {
	        return Long.parseLong(next());
	    }
	    double nextDouble() {
	        return Double.parseDouble(next());
	    }	    
	    BigInteger nextBigInteger() {
	        return new BigInteger(next());
	    }
	    BigDecimal nextBigDecimal() {
	        return new BigDecimal(next());
	    }
	}
}