Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Inverse of Rows and Columns

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given a binary matrix $$$a$$$ of size $$$n \times 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}, \dots, a_{1, m}, a_{2, 1}, a_{2, 2}, \dots, a_{2, m}, \dots, 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 \le n, m \le 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 \le a_{i, j} \le 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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/07/2021 10:08:14 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|