Codeforces Round 742 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

2-sat

constructive algorithms

dfs and similar

dsu

graphs

implementation

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. One-Four Overload

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAlice has an empty grid with $$$n$$$ rows and $$$m$$$ 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 $$$1$$$ or $$$4$$$;
- 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 $$$0$$$);
- every marked cell contains a multiple of $$$5$$$.

Input

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 500$$$) — the number of rows and the number of columns in the grid, respectively.

Then $$$n$$$ lines follow, each containing $$$m$$$ 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 $$$n$$$ lines of $$$m$$$ space-separated integers — the integers in the grid.

Examples

Input

5 5 ..... .XXX. .X.X. .XXX. .....

Output

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

Input

5 5 ..... .XXX. .XXX. .XXX. .....

Output

NO

Input

3 2 .. .. ..

Output

YES 4 1 4 1 1 4

Input

9 9 ......... .XXXXX.X. .X...X... .X.XXXXX. .X.X.X.X. .X.XXX.X. .X.....X. .XXXXXXX. .........

Output

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/05/2024 04:38:16 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|