Background

Tweetuzki’s coach has recently often shared articles about “Yitu Technology” in the group chat. “Yitu Technology” is a Shanghai startup focusing on computer vision technology, and its face recognition technology is at a leading level worldwide. In June 2018, in the global industry gold-standard FRVT test, with a false positive rate of one in ten million, Yitu’s recognition accuracy was close to $99\%$, reaching the best level in the global industry under this metric. This was the second year in a row that Yitu Technology won the championship of this competition, and it was also the first Chinese team to win this competition. On November 16, 2018, the U.S. National Institute of Standards and Technology (NIST) released the latest report of the world’s authoritative face recognition competition (FRVT). Yitu’s algorithm continued to rank first, and with a false positive rate of one in ten million, its recognition accuracy exceeded $99\%$, which is currently the best level of face recognition technology in the world.

More importantly, the founder of Yitu Technology is a graduate of the affiliated high school, and also Tweetuzki’s senior! Face recognition is really hard! Tweetuzki often imagines that if their own program could be even one hundred-millionth as powerful as their seniors’, that would be great.

Problem 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