Problem: Ranks

A finite field F2 consists of two elements: 0 and 1. Addition and multiplication on F2 are those on integers modulo two, as defined below.

| + | 0 | 1
---|---|---
0| 0| 1
1| 1| 0
|  | $\times$ | 0 | 1
---|---|---
0| 0| 0
1| 0| 1



A set of vectors $v_1, ... , v_k$ over F2 with the same dimension is said to be linearly independent when, for $c_1, ... , c_k \in $ F2, $c_1v_1 + ... + c_kv_k = 0$ is equivalent to $c_1 = ... = c_k = 0$, where $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 $ \left[ \begin{array}{rrr} 0 & 0 & 1 \\\ 1 & 0 & 1 \end{array} \right] $ is two; the column vectors $ \left[ \begin{array}{rrr} 0 \\\ 1 \end{array} \right] $ and $ \left[ \begin{array}{rrr} 1 \\\ 1 \end{array} \right] $ (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 F2. For any indices $i$ and $j$, let $A^{(ij)}$ be a matrix equivalent to $A$ except that the $(i, j)$ entry is flipped.

\begin{equation*} A^{(ij)}_{kl}= \left \\{ \begin{array}{ll} A_{kl} + 1 & (k = i \; {\rm and} \; l = j) \\\ A_{kl} & ({\rm otherwise}) \\\ \end{array} \right. \end{equation*}

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$.

Input

The input consists of a single test case of the following format.


$n$ $m$
$A_{11}$ ... $A_{1m}$
.
.
.
$A_{n1}$ ... $A_{nm}$


$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

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.

Sample Input 1


2 3
001
101


Sample Output 1


-0-
-00


Sample Input 2


5 4
1111
1000
1000
1000
1000


Sample Output 2


0000
0+++
0+++
0+++
0+++


Sample Input 3


10 10
1000001001
0000010100
0000100010
0001000001
0010000010
0100000100
1000001000
0000010000
0000100000
0001000001


Sample Output 3


000-00000-
0-00000-00
00-00000-0
+00000+000
00-0000000
0-00000000
000-00000-
0-000-0-00
00-0-000-0
+00000+000


Sample Input 4


1 1
0


Sample Output 4


+






Example

Input

2 3
001
101


Output

-0-
-00

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

#define BIT_N 2002
typedef long long ll;
typedef pair<ll,ll> P;
typedef bitset<BIT_N> Bit;
vector<int> baseNum;

char ans[1001][1001];
ll n,m,ran;

void Gaussian_elimination(vector<Bit> &v){
	int v_size = v.size();
    REP(i, m) {
        int pla = -1;
        for(int j = ran;j < v_size;j++){
            if(v[j][i] == 1){
                pla = j;
                break;
            }
        }

        if(pla != -1){
            swap(v[ran], v[pla]);
            for(int j = 0;j < v_size;j++){
				if(j == ran)continue;
                if(v[j][i] == 1)v[j] ^= v[ran];
            }
            ran++;
        }
    }
}

void makeBaseNum(vector<Bit> v) {
    REP(i,n){
        REP(j,BIT_N){
            if(v[i][j] == 1){
                baseNum.EB(j);
                break;
            }
        }
    }
}

void check(int c, vector<Bit> v){

    vector<int> num = baseNum;
    bool ism = false;
    REP(i,n){
        if(v[i][c] == 1){
            v[i][m] = 1;
            if(num[i] == c){
                do{
                    num[i]++;
                }while(v[i][num[i]] != 1);
            }
        }
        if(num[i] == m)ism = true;
        v[i][c] = 0;
    }

    REP(i,n-1){
        if(num[i] > num[i+1]){
            swap(num[i], num[i+1]);
            swap(v[i], v[i+1]);
        }
    }

    REP(i,n){
        bool pla = false;
        bool mai = false;
        REP(j,n){
            auto tmp = v[j][m] ^ v[j][m + 1 + i];
            if(j >= ran && tmp){
                pla = true;
            }
            if(j == ran - 1 && num[ran - 1] == m && !tmp)mai = true;
        }
        if(ism && !pla && mai){
            ans[i][c] = '-';
        }
        else if(!ism && pla){
            ans[i][c] = '+';
        }
        else {
            ans[i][c] = '0';
        }
    }

}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);

    vector<Bit> v;
    cin >> n >> m;
    REP(i,n){
        Bit tmp;
        REP(j,m){
            char c;cin >> c;
            if(c == '1')tmp[j] = 1;
        }
        v.EB(tmp);
    }

    REP(i,n){
        v[i][m + 1 + i] = 1;
    }

    Gaussian_elimination(v);
    makeBaseNum(v);

    REP(i,m){
        check(i, v);
    }

    REP(i,n){
        REP(j,m){
            cout << ans[i][j];
        }
        cout << "\n";
    }

    return 0;
}