계수

유한체 $\mathbf{F}_2$는 0과 1 두 원소로 이루어진다. $\mathbf{F}_2$의 덧셈과 곱셈은 2로 나눈 나머지에 대한 정수 연산이며, 아래 그림과 같다.

같은 차원을 가진 $\mathbf{F}_2$ 위의 벡터 $\mathbf{v}_1, \ldots, \mathbf{v}_k$가 선형 독립이라는 것은, $c_1, \ldots, c_k \in \mathbf{F}_2$에 대해 $c_1\mathbf{v}_1 + \cdots + c_k\mathbf{v}_k = \mathbf{0}$이 성립하면 반드시 $c_1 = \cdots = c_k = 0$인 경우만 있다는 뜻이다. 여기서 $\mathbf{0}$은 모든 원소가 0인 영벡터이다.

행렬의 계수는 열벡터들로 이루어진 선형 독립 집합의 최대 원소 수이다. 예를 들어 $\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 1 \end{bmatrix}$의 계수는 2이다. 첫 번째 열 $\begin{bmatrix} 0 \\ 1 \end{bmatrix}$과 세 번째 열 $\begin{bmatrix} 1 \\ 1 \end{bmatrix}$은 선형 독립이지만, 세 열 전체는 선형 독립이 아니다. 영행렬의 계수는 0이다.

행렬 $A$에서 $(i, j)$ 원소만 뒤집은 행렬을 $A^{(ij)}$라 하자.

$A_{kl}^{(ij)} = \begin{cases} A_{kl} + 1 & (k = i \text{ and } l = j) \\ A_{kl} & (\text{otherwise}) \end{cases}$

$A$의 계수를 $r$, $A^{(ij)}$의 계수를 $r^{(ij)}$라 할 때, 모든 $(i, j)$에 대해 (i) $r^{(ij)} < r$, (ii) $r^{(ij)} = r$, (iii) $r^{(ij)} > r$ 중 어느 관계인지 구하라.

입력은 다음 형식의 테스트 케이스 하나로 주어진다.

n m
A11 ... A1m
...
An1 ... Anm

$n$과 $m$은 행렬 $A$의 행 수와 열 수이다($1 \le n \le 1000$, $1 \le m \le 1000$). 다음 $n$개 줄에는 $A$의 원소가 공백 없이 나열된다. $A_{ij}$는 $i$행 $j$열의 원소이며 0 또는 1이다.

$n$개 줄을 출력한다. 각 줄은 $m$개의 문자로 이루어진다. $i$번째 줄의 $j$번째 문자는 반드시 -, 0, + 중 하나여야 하며, 각각 (i), (ii), (iii)의 경우에 대응한다.