Problem: You are given a binary matrix a of size n × m. A binary matrix is a matrix where each element is either 0 or 1.

You may perform some (possibly zero) operations with this matrix. During each operation you can inverse the row of this matrix or a column of this matrix. Formally, inverting a row is changing all values in this row to the opposite (0 to 1, 1 to 0). Inverting a column is changing all values in this column to the opposite.

Your task is to sort the initial matrix by some sequence of such operations. The matrix is considered sorted if the array [a_{1, 1}, a_{1, 2}, ..., a_{1, m}, a_{2, 1}, a_{2, 2}, ..., a_{2, m}, ..., a_{n, m - 1}, a_{n, m}] is sorted in non-descending order.

Input

The first line of the input contains two integers n and m (1 ≤ n, m ≤ 200) — the number of rows and the number of columns in the matrix.

The next n lines contain m integers each. The j-th element in the i-th line is a_{i, j} (0 ≤ a_{i, j} ≤ 1) — the element of a at position (i, j).

Output

If it is impossible to obtain a sorted matrix, print "NO" in the first line.

Otherwise print "YES" in the first line. In the second line print a string r of length n. The i-th character r_i of this string should be '1' if the i-th row of the matrix is inverted and '0' otherwise. In the third line print a string c of length m. The j-th character c_j of this string should be '1' if the j-th column of the matrix is inverted and '0' otherwise. If there are multiple answers, you can print any.

Examples

Input


2 2
1 1
0 1


Output


YES
00
10


Input


3 4
0 0 0 1
0 0 0 0
1 1 1 1


Output


YES
010
0000


Input


3 3
0 0 0
1 0 1
1 1 0


Output


NO

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;


public class Main {

	static class Task {
		
		int NN = 300001;
		int MOD = 1000000007;
		int INF = 2000000000;
		long INFINITY = 2000000000000000000L;
		
		public void solve(InputReader in, PrintWriter out) {
			int n = in.nextInt(), m = in.nextInt();
			int [][] a = new int[n][m];
			int [][] b = new int[n][m];
			for(int i=0;i<n;++i) {
				for(int j=0;j<m;++j) {
					a[i][j] = in.nextInt();
				}
			}
			if(n == 1) {
				out.println("YES");
				out.println("0");
				for(int j=0;j<m;++j) {
					if(a[0][j] == 1) {
						out.print("1");
					} else {
						out.print("0");	
					}
				}
				out.println();return;
			}
			for(int targetRow=0;targetRow<n;++targetRow) {
				StringBuilder r = new StringBuilder();
				StringBuilder c = new StringBuilder();
				int startR = -1, startC = -1;
				for(int i=0;i<n;++i) {
					r.append("0");
					for(int j=0;j<m;++j) {
						if(a[i][j] == 1 && i < targetRow) {
							startR = i;startC = j;
						}
						if(a[i][j] == 0 && i > targetRow) {
							startR = i;startC = j;
						}
						if(i == 0) {
							c.append("0");
						}
					}
				}
				if(startR == -1) {
					if(isValidPattern(targetRow, n, m, a)) {
						out.println("YES");
						out.println(r.toString());
						out.println(c.toString());
						return;
					} else {
						continue;
					}
				}
				boolean valid = true;
				for(int i=0;i<n;++i) {
					for(int j=0;j<m;++j) {
						b[i][j] = a[i][j];
					}
				}
				r.setCharAt(startR, '1');
				for(int j=0;j<m;++j) {
					b[startR][j] = 1 - b[startR][j];
					if((startR < targetRow && b[startR][j] == 1) ||
							(startR > targetRow && b[startR][j] == 0)) {
						c.setCharAt(j, '1');
						for(int i=0;i<n;++i) {
							b[i][j] = 1 - b[i][j];
							if((i < targetRow && b[i][j] == 1) ||
									(i > targetRow && b[i][j] == 0)) {
								if(r.charAt(i) == '1') {
									valid = false;break;
								}
								r.setCharAt(i, '1');
								for(int jj=0;jj<m;++jj) {
									b[i][jj] = 1 - b[i][jj];
								}
							}
						}
						if(!valid)
							break;
					}
				}
				if(valid) {
					if(isValidPattern(targetRow, n, m, b)) {
						out.println("YES");
						out.println(r.toString());
						out.println(c.toString());
						return;						
					}
				}
				valid = true;
				for(int i=0;i<n;++i) {
					r.setCharAt(i, '0');
					for(int j=0;j<m;++j) {
						b[i][j] = a[i][j];
						if(i==0) {
							c.setCharAt(j, '0');
						}
					}
				}
				c.setCharAt(startC, '1');
				for(int i=0;i<n;++i) {
					b[i][startC] = 1 - b[i][startC];
					if((i < targetRow && b[i][startC] == 1) ||
							(i > targetRow && b[i][startC] == 0)) {
						r.setCharAt(i, '1');
						for(int j=0;j<m;++j) {
							b[i][j] = 1 - b[i][j];
							if((i < targetRow && b[i][j] == 1) ||
									(i > targetRow && b[i][j] == 0)) {
								if(c.charAt(j) == '1') {
									valid = false;break;
								}
								c.setCharAt(j, '1');
								for(int ii=0;ii<n;++ii) {
									b[ii][j] = 1 - b[ii][j];
								}
							}
						}
						if(!valid)
							break;
					}
				}
				if(valid) {
					if(isValidPattern(targetRow, n, m, b)) {
						out.println("YES");
						out.println(r.toString());
						out.println(c.toString());
						return;						
					}
				}
			}
			out.println("NO");
		}
		
		boolean isValidPattern(int t, int n, int m, int [][] arr) {
			for(int i=0;i<n;++i) {
				if(i == t)
					continue;				
				for(int j=0;j<m;++j) {
					if(i < t && arr[i][j] == 1)
						return false;
					if(i > t && arr[i][j] == 0)
						return false;
				}				
			}
			for(int j=0;j+1<m;++j) {
				if(arr[t][j] == 1 && arr[t][j+1] == 0) {
					return false;
				}
			}
			return true;
		}
		
	}
	
	static void prepareIO(boolean isFileIO) {
		//long t1 = System.currentTimeMillis();
		Task solver = new Task();
		// Standard IO
		if(!isFileIO) { 
			InputStream inputStream = System.in;
	        OutputStream outputStream = System.out;
	        InputReader in = new InputReader(inputStream);
	        PrintWriter out = new PrintWriter(outputStream);
	        solver.solve(in, out);
	        //out.println("time(s): " + (1.0*(System.currentTimeMillis()-t1))/1000.0);
	        out.close();
		}
        // File IO
		else {
			String IPfilePath = System.getProperty("user.home") + "/Downloads/ip.in";
	        String OPfilePath = System.getProperty("user.home") + "/Downloads/op.out";
	        InputReader fin = new InputReader(IPfilePath);
	        PrintWriter fout = null;
	        try {
				fout = new PrintWriter(new File(OPfilePath));
			} catch (FileNotFoundException e) {
				e.printStackTrace();
			}
	        solver.solve(fin, fout);
	        //fout.println("time(s): " + (1.0*(System.currentTimeMillis()-t1))/1000.0);
	        fout.close();
		}
	}
	
	public static void main(String[] args) {
        prepareIO(false);
	}
	
	static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        
        public InputReader(String filePath) {
        	File file = new File(filePath);
            try {
				reader = new BufferedReader(new FileReader(file));
			} catch (FileNotFoundException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
            tokenizer = null;
        }
        
        public String nextLine() {
        	String str = "";
        	try {
				str = reader.readLine();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
        	return str;
        }
        
        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
        	return Double.parseDouble(next());
        }
        
    }

}