One-Four Overload codeforces solution – Alice has an empty grid with nn rows and mm columns. Some of the cells are marked

 

One-Four Overload codeforces solution


Alice has an empty grid with nn rows and mm columns. Some of the cells are marked, and no marked cells are adjacent to the edge of the grid. (Two squares are adjacent if they share a side.)

Alice wants to fill each cell with a number such that the following statements are true:

  • every unmarked cell contains either the number 11 or 44;
  • every marked cell contains the sum of the numbers in all unmarked cells adjacent to it (if a marked cell is not adjacent to any unmarked cell, this sum is 00);
  • every marked cell contains a multiple of 55.

Alice couldn’t figure it out, so she asks Bob to help her. Help Bob find any such grid, or state that no such grid exists.

Input

The first line of input contains two integers nn and mm (1n,m5001≤n,m≤500) — the number of rows and the number of columns in the grid, respectively.

Then nn lines follow, each containing mm characters. Each of these characters is either ‘.‘ or ‘X‘ — an unmarked and a marked cell, respectively. No marked cells are adjacent to the edge of the grid.

Output

Output “‘NO” if no suitable grid exists. Otherwise, output “‘YES“‘. Then output nn lines of mm space-separated integers — the integers in the grid.

Examples One-Four Overload codeforces solution

input One-Four Overload codeforces solution

Copy One-Four Overload codeforces solution

5 5
.....
.XXX.
.X.X.
.XXX.
.....
YES
4 1 4 4 1
4 5 5 5 1
4 5 1 5 4
1 5 5 5 4
1 4 4 1 4
5 5
.....
.XXX.
.XXX.
.XXX.
.....
9 9
.........
.XXXXX.X.
.X...X...
.X.XXXXX.
.X.X.X.X.
.X.XXX.X.
.X.....X.
.XXXXXXX.
.........
YES
4 4 4 1 4 1 4 1 4
1 5 5 5 5 5 4 10 1
4 5 1 4 1 5 4 4 4
4 5 1 5 5 0 5 5 1
4 5 1 5 4 5 1 5 4
4 5 1 5 5 5 4 5 1
1 5 4 4 1 1 4 5 1
4 5 5 5 5 5 5 5 4
1 1 1 1 4 4 1 1 4

Note

It can be shown that no such grid exists for the second test.


 

Leave a Reply

Your email address will not be published. Required fields are marked *

*