CF616C.The Labyrinth

You are given a rectangular field of n × m cells. Each cell is either empty or impassable (contains an obstacle). Empty cells are marked with '.', impassable cells are marked with '*'. Let's call two empty cells adjacent if they share a side.

Let's call a connected component any non-extendible set of cells such that any two of them are connected by the path of adjacent cells. It is a typical well-known definition of a connected component.

For each impassable cell (x, y) imagine that it is an empty cell (all other cells remain unchanged) and find the size (the number of cells) of the connected component which contains (x, y). You should do it for each impassable cell independently.

The answer should be printed as a matrix with n rows and m columns. The j-th symbol of the i-th row should be "." if the cell is empty at the start. Otherwise the j-th symbol of the i-th row should contain the only digit —- the answer modulo 10. The matrix should be printed without any spaces.

To make your output faster it is recommended to build the output as an array of n strings having length m and print it as a sequence of lines. It will be much faster than writing character-by-character.

As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.

给你一个 $n \times m$ 的矩形网格。每个格子要么为空，要么为不可通行（含障碍物）。空格子用 . 表示，不可通行格子用 * 表示。若两个空格子共享一条边，则称它们相邻。

我们称一个连通块为一个极大格子集合，使得该集合中任意两个格子均可通过一系列相邻的空格子相互连通。这是连通块的标准定义。

对每个不可通行格子 $(x, y)$，我们假设它变为一个空格子（其余所有格子保持不变），然后求出包含 $(x, y)$ 的连通块的大小（即其中所含格子的数量）。你需要对每个不可通行格子独立地完成这一计算。

输出应为一个 $n$ 行 $m$ 列的矩阵。第 $i$ 行第 $j$ 列的字符应为：若初始时该格子为空，则输出 .；否则（即该格子初始为不可通行格子），输出一个唯一数字——该连通块大小对 $10$ 取模的结果。整个矩阵应直接输出，不包含任何空格。

为加快输出速度，建议将输出构造成一个长度为 $n$ 的字符串数组，其中每个字符串长度为 $m$，然后按行依次输出。这种方式比逐个字符输出要快得多。

由于输入/输出规模可能非常大，建议使用快速输入/输出方法：例如，在 C++ 中优先使用 scanf/printf 而非 cin/cout；在 Java 中优先使用 BufferedReader/PrintWriter 而非 Scanner/System.out。

The first line contains two integers n, m (1 ≤ n, m ≤ 1000) — the number of rows and columns in the field.

Each of the next n lines contains m symbols: "." for empty cells, "*" for impassable cells.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 1000$）—— 分别表示场地的行数和列数。

接下来的 $n$ 行中，每行包含 $m$ 个字符：“.” 表示空单元格，“*” 表示不可通行的单元格。

Print the answer as a matrix as described above. See the examples to precise the format of the output.

按上述描述输出答案矩阵。参见示例以明确输出格式。

In first example, if we imagine that the central cell is empty then it will be included to component of size 5 (cross). If any of the corner cell will be empty then it will be included to component of size 3 (corner).

在第一个例子中，如果我们假设中心格子为空，则它将被包含在大小为 5 的连通块中（十字形）。如果任意一个角上的格子为空，则它将被包含在大小为 3 的连通块中（角形）。