붕어빵 타이쿤

성지는 몰래 붕어빵 타이쿤 게임을 즐기고 있다. 이 게임은 조금 특별하다.

격자는 M행 N열로 이루어져 있고, 각 칸에는 붕어빵 하나가 놓여 있다. 각 붕어빵은 앞면이 위를 향하거나 뒷면이 위를 향한다. 한 칸을 누르면 그 칸의 붕어빵과 상하좌우로 인접한 붕어빵들이 동시에 뒤집힌다. 격자 밖에 있는 칸은 무시한다.

모든 붕어빵을 꺼내려면 모든 붕어빵의 앞면이 위를 향해야 한다. 가능한 한 적은 칸을 눌러 모든 붕어빵을 앞면이 위로 보이게 만드는 방법을 구하자.

첫째 줄에 격자의 세로 크기 M과 가로 크기 N이 주어진다. (1 ≤ M ≤ 15, 1 ≤ N ≤ 15)

둘째 줄부터 M개의 줄에는 각 줄마다 N개의 정수 0 또는 1이 주어진다. 0은 현재 앞면이 위로 보이는 붕어빵, 1은 현재 뒷면이 위로 보이는 붕어빵을 의미한다.

모든 붕어빵의 앞면을 위로 만들 수 있다면 M개의 줄에 N개의 숫자를 출력한다. 각 숫자는 해당 칸을 누르면 1, 누르지 않으면 0이다.

출력하는 방법은 누르는 칸의 개수가 최소여야 한다. 최소 방법이 여러 개라면 위쪽 행부터, 같은 행에서는 왼쪽 칸부터 읽었을 때 사전순으로 가장 앞서는 방법을 출력한다.

가능한 방법이 없으면 IMPOSSIBLE을 출력한다.

처음에 (2, 1)을 누르면 다음 상태가 된다.

0 0 0 11 0 1 01 1 1 01 0 0 1

그다음 (2, 4)를 누르면 다음 상태가 된다.

0 0 0 01 0 0 11 1 1 11 0 0 1

그다음 (3, 1)을 누르면 다음 상태가 된다.

0 0 0 00 0 0 10 0 1 10 0 0 1

마지막으로 (3, 4)를 누르면 모든 칸이 0이 된다.

0 0 0 00 0 0 00 0 0 00 0 0 0

다음 방법도 가능하지만, 사전순으로 더 뒤에 있으므로 정답으로 출력하지 않는다.

0 1 1 00 0 0 00 0 0 00 1 1 0