The LCS (Longest Common Subsequence) algorithm of two binary strings $A$ and $B$ returns a matrix as follows:
Given a matrix $M$, find the smallest among all possible pairs of binary strings $A$ and $B$ such that LCS(A, B) returns $M$. A pair $(A, B)$ is smaller than $(C, D)$ if $(A+B)$ is lexicographically smaller than $(C+D)$ where the operator $+$ denotes standard string concatenation.
Input
First line of the input contains two integers $n$ and $m$ $(1 \le n, m \le 2 \cdot 10^3)$, the number of rows and the number of columns in the matrix.
Next $n$ lines contain $m$ integers each. The $j$-th element in the $i$-th line is $M[i][j]$.
It is guaranteed that there exists at least two binary strings such that the LCS algorithm returns the given matrix.
Please note that the given matrix differs from the one at the pseudocode by not having the row number 0 and column number 0 for simplicity.
Output
Print one binary string $A$ of length $n$ on the first line and one binary string $B$ of length $m$ on the second line, such that the pair $(A, B)$ is the smallest lexicographically where the LCS algorithm returns the given matrix.