Map

The 2D map of the world has the shape of a matrix with $m$ lines and $n$ columns. On this map, the countries are labelled with numbers $1, 2, 3, \dots$. The countries have the shape of a square with the side $1$ or a rectangle made of two adjacent squares with the side $1$. There can be only one superpower, a country which is made of $3$ adjacent squares of side $1$. Two countries can be considered neighbours if they have at least a common side.

In the scheme on the right, we have a $4 \times 5$ sized map, which contains $11$ countries (the country $1$ is a superpower). Our purpose is to paint the countries on the map, so that each country should have a different colour from all its neighbours. A possible colouring is presented in the scheme on the right.

Task

Paint the countries on the map in maximum four colours, codified with $1$, $2$, $3$, $4$, so that two neighbouring countries should have different colours.

Input data

The first line contains the values of $m$ and $n$ separated by a space, representing the number of lines and the number of columns of the map. Each of the following $m$ lines contains $n$ natural numbers different from zero separated by one or more spaces, and together, they form the map of the world, with countries counted $1, 2, 3, \dots$.

Output data

A matrix with $m$ lines and $n$ columns will be displayed, containing a possible painting of the map, as it is defined above. The numbers on a line will be separated from each other by a space.

Constraints and clarifications

• $2 \leq m, n \leq 1 \ 000$
• Any correct solution is accepted.
• A valid painting can contain $4$ or fewer colours.
• The test cases are not the same as the ones used in the contest, so the scores might be slightly different from these obtained in the real contest.

Example 1

stdin

4 5
1 1 1 2 9
3 3 4 2 9
5 6 4 7 10
5 6 8 8 11

stdout

3 3 3 4 3
1 1 2 4 3
4 3 2 3 4
4 3 4 4 1

Explanation

The countries $3$ and $11$ are painted using colour $1$.
The country $4$ is painted using colour $2$.
The countries $1$, $6$, $7$ and $9$ are painted using colour $3$.
The countries $2$, $5$, $8$ and $10$ are painted using colour $4$.

Example 2

stdin

3 3
1 2 3
5 4 9
6 8 7

stdout

1 2 1
2 1 2
1 2 1

Explanation

All the countries are squares with the side $1$. In this case, all the countries can be painted using only two colours.