Farmer John knows that an intellectually satisfied cow is a happy cow who will give more milk. He has arranged a brainy activity for cows in which they manipulate an M× N grid (1 ≤ M ≤ 15; 1 ≤ N ≤ 15) of square tiles, each of which is colored black on one side and white on the other side.

As one would guess, when a single white tile is flipped, it changes to black; when a single black tile is flipped, it changes to white. The cows are rewarded when they flip the tiles so that each tile has the white side face up. However, the cows have rather large hooves and when they try to flip a certain tile, they also flip all the adjacent tiles (tiles that share a full edge with the flipped tile). Since the flips are tiring, the cows want to minimize the number of flips they have to make.

Help the cows determine the minimum number of flips required, and the locations to flip to achieve that minimum. If there are multiple ways to achieve the task with the minimum amount of flips, return the one with the least lexicographical ordering in the output when considered as a string. If the task is impossible, print one line with the word "IMPOSSIBLE".

Input

Line 1: Two space-separated integers: M and N 
Lines 2.. M+1: Line i+1 describes the colors (left to right) of row i of the grid with N space-separated integers which are 1 for black and 0 for white

Output

Lines 1.. M: Each line contains N space-separated integers, each specifying how many times to flip that particular location.

Sample Input

4 4
1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Sample Output

0 0 0 0
1 0 0 1
1 0 0 1
0 0 0 0
import java.util.*;
public class Main {
    final static int M= 16;
    static int[][] g = new int[M][M];//待翻转数组
    static int[][] t = new int[M][M];//g的副本
    static int[][] f = new int[M][M];
    static int cnt;//每种方案的翻转次数
    static int n,m;//网格大小
    static int[][] move = {{0,-1},{0,1},{1,0},{-1,0}};
    static void flip(int i,int j) {//翻转
        ++cnt;//步数加1
        f[i][j] = 1;//记录翻转了哪个瓷砖
        t[i][j] ^= 1;//首先翻转自己
        for(int k = 0;k < 4;k++) //向四个方向寻找,找到就翻转
            if(i + move[k][0] > -1 && j + move[k][1] > -1)
                t[i + move[k][0]][j + move[k][1]] ^= 1;
    }
    static boolean ok(int k) {//对于第一行的每一种情况,判断是否能够产生最终的结果 
        cnt = 0;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                t[i][j] = g[i][j];
        for(int j = 0;j < m;j++) 
            if((k & (1 << (m - 1 - j))) != 0)//对于k的每一个取值,如1010,找到不为0的列,因为只需要翻转1就可以了
                flip(0,j);
        for(int i = 1;i < n;i++)//当第一行全部翻转完了,原来为1的位置肯定是0,原来是0的位置肯定是1,这就需要第二行来解决这些为1位置,以此类推 
            for(int j = 0;j < m;j++)
                if(t[i - 1][j] != 0)//如果该列上一个位置是1,那么这个位置需要翻,否则不需要翻
                    flip(i,j);
        for(int j = 0;j < m;j++)//单独考虑最后一行
            if(t[n - 1][j] != 0)
                return false;
        return true;
    }
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while(cin.hasNext()) {
            int p;//记录当前最佳方案第一行的翻转方案
            int ans;//记录当前最佳方案的翻转次数
            n = cin.nextInt();
            m = cin.nextInt();
            for(int i = 0;i < n;i++) 
                for(int j = 0;j < m;j++) 
                    g[i][j] = cin.nextInt();
            
            ans = m * n + 1;p = -1;
            for(int i = 0;i < (1 << m);i++) //用来枚举第一行的各种不同翻法,如0001就是只翻最后一个
                if(ok(i) && cnt < ans) {//如果找到一种可能并且所用的步数更少的话,记下这种翻法
                    ans = cnt;
                    p = i;
                }
            for(int i = 0;i < n;i++)
                for(int j = 0;j < m;j++)
                    f[i][j] = 0;
            if(p >= 0) {//最后找到的就是最少的翻法,模拟一遍,然后输出
                ok(p);
                for(int i = 0;i < n;i++)
                    for(int j = 0;j < m;j++)
                        if(j < m - 1)
                            System.out.print(f[i][j] + " ");
                        else
                            System.out.print(f[i][j] + "\n");
            } else 
                System.out.print("IMPOSSIBLE");
        }
    }
}