P14901 [ICPC 2018 Yokohama R] Ranks

A finite field $\mathbf{F}_2$ consists of two elements: $0$ and $1$. Addition and multiplication on $\mathbf{F}_2$ are those on integers modulo two, as defined below. |||| |:-:|:-:|:-:| |$\boldsymbol{+}$|$\mathbf{0}$|$\mathbf{1}$| |$\mathbf{0}$|$\mathbf{0}$|$\mathbf{1}$| |$\mathbf{1}$|$\mathbf{1}$|$\mathbf{0}$| |||| |:-:|:-:|:-:| |$\boldsymbol{\times}$|$\mathbf{0}$|$\mathbf{1}$| |$\mathbf{0}$|$\mathbf{0}$|$\mathbf{0}$| |$\mathbf{1}$|$\mathbf{0}$|$\mathbf{1}$| A set of vectors $\mathbf{v}_1, \ldots, \mathbf{v}_k$ over $\mathbf{F}_2$ with the same dimension is said to be **linearly independent** when, for $c_1, \ldots, c_k \in \mathbf{F}_2$, $c_1 \mathbf{v}_1 + \cdots + c_k \mathbf{v}_k = \mathbf{0}$ is equivalent to $c_1 = \cdots = c_k = 0$, where $\mathbf{0}$ is the zero vector, the vector with all its elements being zero. The **rank** of a matrix is the maximum cardinality of its linearly independent sets of column vectors. For example, the rank of the matrix $\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix}$ is two; the column vectors $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$ and $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ (the first and the third columns) are linearly independent while the set of all three column vectors is **not** linearly independent. Note that the rank is zero for the zero matrix. Given the above definition of the rank of matrices, the following may be an intriguing question. How does a modification of an entry in a matrix change the rank of the matrix? To investigate this question, let us suppose that we are given a matrix $A$ over $\mathbf{F}_2$. For any indices $i$ and $j$, let $A^{(ij)}$ be a matrix equivalent to $A$ except that the $(i,j)$ entry is flipped. $$ A^{(ij)}_{kl} = \begin{cases} A_{kl} + 1 & (k = i \text{ and } l = j) \\ A_{kl} & (\text{otherwise}) \end{cases} $$ In this problem, we are interested in the rank of the matrix $A^{(ij)}$. Let us denote the rank of $A$ by $r$, and that of $A^{(ij)}$ by $r^{(ij)}$. Your task is to determine, for all $(i,j)$ entries, the relation of ranks before and after flipping the entry out of the following possibilities: (i) $r^{(ij)} < r$, (ii) $r^{(ij)} = r$, or (iii) $r^{(ij)} > r$.

The input consists of a single test case of the following format. $$ \begin{aligned} & n \; m \\ & A_{11} \ldots A_{1m} \\ & \vdots \\ & A_{n1} \ldots A_{nm} \end{aligned} $$ $n$ and $m$ are the numbers of rows and columns in the matrix $A$, respectively ($1 \leq n \leq 1000$, $1 \leq m \leq 1000$). In the next $n$ lines, the entries of $A$ are listed without spaces in between. $A_{ij}$ is the entry in the $i$-th row and $j$-th column, which is either $0$ or $1$.

Output $n$ lines, each consisting of $m$ characters. The character in the $i$-th line at the $j$-th position must be either $-$ (minus), $0$ (zero), or $+$ (plus). They correspond to the possibilities (i), (ii), and (iii) in the problem statement respectively.