Problem Background

Tweetuzki's coach frequently shares articles about "Yitu Technology" in the group. "Yitu Technology" is a Shanghai-based startup focused on computer vision technology, particularly in facial recognition. In June 2018, Yitu achieved an accuracy rate close to $99\%$ under a false positive rate of one in ten million in the FRVT test, the best industrial standard globally. This marked the second consecutive year Yitu won this competition, and it was the first time a Chinese team had won. On November 16, 2018, the National Institute of Standards and Technology (NIST) in the USA released the latest report of the global authoritative facial recognition competition (FRVT), where Yitu's algorithm maintained the top position with an accuracy rate exceeding $99\%$ under a false positive rate of one in ten million, setting the best record in global facial recognition technology.

More importantly, the founder of Yitu Technology is an alumnus of the affiliated high school—a senior to Tweetuzki! Facial recognition is indeed challenging! Tweetuzki often fantasizes about how great it would be if his programs could be a tiny fraction as capable as his seniors.

Problem Description

Tweetuzki wants to design a program that can recognize hidden numbers in an input matrix.

The input is an $r \times c$ character matrix, where each element is either . or #. The # characters form some numbers. The input matrix strictly adheres to the following rules:

• Except for the digit $1$ which occupies a $5 \times 1$ rectangular area, all other digits occupy a $5 \times 3$ rectangular area.

• Adjacent numbers are separated by at least one column of ., meaning numbers do not touch each other; and numbers are only arranged horizontally, not vertically. These rules can be summarized as: for two numbers $A$ and $B$ (with $A$ on the left of $B$), if their horizontal extents are $[l_A, r_A]$ and $[l_B, r_B]$ respectively, then $l_B \ge r_A + 2$ must hold.

• The composition of the digits strictly follows the pattern below:

```plain
Digit composition:
# # # # # # # # . # # # # # # # # # # # # # # # # # # #
# . . # . . # # . # # . . # . . . . # # . # # . # # . #
# # # # # # # # # # # # # # # # . . # # # # # # # # . #
# # . . . . # . . # . . # # . # . . # # . # . . # # . #
# # # # # # # . . # # # # # # # . . # # # # # # # # # #

Represented digits:
1 2 3 4 5 6 7 8 9 0
```

Digits do not tilt, enlarge, or shrink. See the sample cases for specifics.

• Apart from the rectangular areas forming the digits, the rest of the matrix is filled with .. It is guaranteed that all connected components of # will form valid digits and adhere to the above rules.

Since Tweetuzki is not very skilled, he seeks your help. Can you assist Tweetuzki in solving this problem?

Input Format

The first line contains two positive integers $r, c$ $(5 \le r \le 10, 3 \le c \le 10^5)$, representing the number of rows and columns of the matrix.
The next $r$ lines each contain $c$ characters separated by spaces, consisting only of . and #. The input matrix is guaranteed to be valid and contain hidden digits.

Output Format

Output a single line containing a string of digits, in order, representing the hidden digits in the matrix.

Sample Input and Output

Sample Input #1

6 10
# . . . . . # . . #
# . . . # . # . . #
# . . . # . # . . #
# . . . # . # . . #
# . . . # . # . . #
. . . . # . . . . .

Sample Output #1

1111

Sample Input #2

8 37
. . . # # # . . . . . . . . . . . . . . . . . . # # # . # . . . . . . . .
. # . # . # . . . . . . . . # # # . . . . . . . # . # . # . . . . . . . .
. # . # # # . . . . . . . . # . . . # # # . . . # # # . # . . # # # . . .
. # . . . # . . . # # # . . # # # . # . # . . . # . # . # . . . . # . . .
. # . # # # . . . . . # . . # . # . # . # . . . # # # . # . . . . # . . .
. # . . . . . . . # # # . . # # # . # . # . . . . . . . . . . . . # . . .
. . . . . . . . . # . . . . . . . . # # # . . . . . . . . . . . . # . . .
. . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . .

Sample Output #2

19260817

Sample Input #3

9 94
# # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . . . . . . . . . . . . . . . . . . . . . . # . # . . . . . . . . . . # . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . # . . . . . . . . . . . . . . . # # # . . # . # . . . . . . . . . . # # # . . . . . . . . . # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# . # . . . # . . # # # . . . . . . . . . . . . # . . # # # . . . . . . . . . . . . # . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
# # # . . . # . . . . # . . . . . . . . . . # # # . . . . # . . . . . . . . . . # # # . . . . . . . . . # . # . . . . . . . # # # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .
. . . . . . # . . # # # . . . . . . . . . . . . # . . . . # . . . . . . . . . . . . . . . . . . . . . . # # # . . . . . . . . . # . . . . . . # . # . . . . . . . . . # . # . . . . . . . .
. . . . . . # . . # . . . . . . . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .
. . . . . . . . . # # # . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # . # . . . . . . . . . . . # . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . # . . . . . . # # # . . . . . . . . . # # # . . . . . . . .

Sample Output #3

0123456789

Notes

Sample Explanation

It is recommended to copy the input into a text editor (or any IDE) and view it with a monospaced font.

Subtasks

Subtask #1 (30 points): The matrix contains only the digit $1$.
Subtask #2 (30 points): The matrix does not contain the digits $1$ and $4$.
Subtask #3 (40 points): No special properties.

见题面 Input 部分

见题面 Output 部分