In the small country of Bytelandia there are $N$ cities. In between certain pairs of cities there exist bidirectional roads.

The King of Bytelandia is looking to enforce tariffs on these roads. For each road, he wants to assign one of the two noble houses to collect taxes on trade passing through that road. However, the King also has a secret secondary goal: to prevent either of the noble houses from staging a rebellion.

If a noble house starts a rebellion, it will succeed if and only if the house can supply weapons to all cities within Bytelandia using at most $K$ weapon factories. To achieve this, the house must select up to $K$ cities as weapon factories, and every city must be reachable from at least one factory via roads assigned to that house. If a house tries to transport weapons on a road controlled by the other house, their rebellion will be detected.

The King has come to you to find a road assignment such that no noble house will be able to form a successful rebellion.

Constraints

$2\le N\le 3000$

For all $i,j$, $a_{i,i}=0,a_{i,j}=a_{j,i}$

$1\le K\le 2$

Subtask 1 [10%]

$K=1$

Subtask 2 [30%]

$K=2$

$N\le 60$

Subtask 3 [40%]

$K=2$

$N\le 500$

Subtask 4 [20%]

$K=2$

Input specification

The first line will contain two space seperated integers: $N$ and $K$.

The next $N$ lines will each contain a binary string of $N$ digits $a_{i,j}$.
These represent the adjacency matrix of the kingdom, with $a_{i,j}=1$ iff cities $i$ and $j$ are directly connected by a road.

Output specification

If no valid assignment exists, output the string IMPOSSIBLE.

Otherwise output the string POSSIBLE, following by $N$ strings of $N$ digits $b_{i,j}$ satisfying $0\le b_{i,j}\le 2$.

$b_{i,j}=0$ denotes that there is no road between $i$ and $j$ (i.e. exactly when $a_{i,j}=0$).

$b_{i,j}=1$ denotes that noble house $1$ controls the road between $i$ and $j$.

$b_{i,j}=2$ denotes that noble house $2$ controls the road between $i$ and $j$.

You must satisfy $b_{i,j}=b_{j,i}$ for all $i,j$.

If multiple valid assignments exist, any will be accepted.

Sample Input 1

3 1
011
101
110

Sample Output 1

IMPOSSIBLE

Sample Input 2

6 2
010001
101000
010100
001010
000101
100010

Sample Output 2

POSSIBLE
010002
102000
020100
001020
000201
200010

Explanation for Sample Output 2

The graph edges can be visualized in the following graph, where red and blue edges denote paths controlled by a given house.

It's clear that in the graph of blue edges no two nodes are sufficient to supply the entire rebellion, and the same holds for the graph of red edges.

Note

Due to subtask interactions, the samples are flipped in order. Samples 1 and 2 correspond to testcases #6 and #2 respectively.