Description

Tweetuzki wants to design a program that can recognize the digits hidden in the input matrix.

The input is a $r \times c$ character matrix. Each element is either . or #. The # symbols can form some digits. The input matrix will strictly follow the rules below:

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

• There is at least one column of . between two adjacent digits, meaning digits will not stick together. Also, digits are only placed left to right, never stacked vertically. Combining these two points: for two digits $A$ and $B$ (with $A$ to the left of $B$), if their horizontal spans are $[l_A, r_A]$ and $[l_B, r_B]$, then it must hold that $l_B \ge r_A + 2$.

• Digits are composed exactly as listed below:

  Digit patterns:
  #   # # #   # # #   # # #   # . #   # # #   # # #   # # #   # # #   # # # 
  #   . . #   . . #   # . #   # . #   # . .   # . .   . . #   # . #   # . # 
  #   # # #   # # #   # # #   # # #   # # #   # # #   . . #   # # #   # . # 
  #   # . .   . . #   . . #   . . #   # . #   # . #   . . #   # . #   # . # 
  #   # # #   # # #   . . #   # # #   # # #   # # #   . . #   # # #   # # # 
  
  Digits represented:
  1     2       3       4       5       6       7       8       9       0
  

  Digits will not be slanted, enlarged, or reduced. See the samples for details.

• Except for the rectangular areas that form digits, all other positions are filled with .. It is guaranteed that every connected component of # can form a digit and that all the rules above are satisfied.

Since Tweetuzki is too weak, they ask you for help. Can you, the smart one, help Tweetuzki solve 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.
Next come $r$ lines. Each line contains $c$ characters separated by spaces, and they are guaranteed to be only . and #. The input matrix is guaranteed to be valid and must contain hidden digits.

Output Format

Output exactly one line containing a string consisting only of digits, outputting the hidden digits in this matrix in order.

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

1111

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

19260817

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

0123456789

Hint

Sample Explanation

It is recommended to copy it into Notepad (or various IDEs) and view it with a monospaced font.

Subtasks

Subtask #1 (30 points): The matrix contains only digit $1$.
Subtask #2 (30 points): The matrix contains no digit $1$ or $4$.
Subtask #3 (40 points): No special properties.

Translated by ChatGPT 5