P15297 [ROI 2012 Day 1] calendar Ancient Calendar

Translation source: [loj #5458. 「ROI 2012 Day 1」Ancient Calendar](https://loj.ac/p/5458).

As everyone knows, in 2012 humans showed great interest in ancient calendars. Especially interesting were those calendars that did not end in 2012. Archaeologists in Tatarstan made an amazing discovery in this area. They found a rectangular stone tablet in an ancient tomb. After decoding the preserved symbols, they recorded it as a table with $N$ rows, each containing $M$ decimal digits. However, the tablet could not be fully decoded because some digits had been worn away. The missing digits in the table are replaced by the symbol `*`. The archaeologists believe that this tablet is an ancient calendar, where the $M$ digits represent the day number for consecutive days within a certain period. The first digit string is the number of the first day in that period, and each following one is larger than the previous by $1$. According to this calendar, the end of the world does not exist: after the day number consisting of $M$ nines, the next day number is the one consisting of $M$ zeros. You need to write a program to restore the missing digits so that, starting from the second row, each number is greater than the number in the previous row by $1$, and output the number of the first day in the found calendar.

The first line of the input file contains two natural numbers $N$ and $M$ $(1 \leq N \leq 100000, 1 \leq M \leq 100000, M \times N \leq 100000)$, representing the number of rows in the table and the length of each row. The next $N$ lines each contain $M$ characters, consisting only of decimal digits $0$ to $9$ and the symbol `*`.

The output file should contain one line consisting of $M$ digits, representing the number of the first day in the calendar. If there are multiple ways to restore it, you may output any one. It is guaranteed that at least one restoration exists.

The detailed additional constraints and scores for subtasks are shown in the table below. | Subtask | Score | Additional Constraints | Notes | | :----: | :--: | :-------------------: | :---: | | $1$ | $40$ | $1 \leq N \leq 1000$, $1 \leq M \leq 100$, each column has at least one preserved digit | You must pass all test points in this subtask to get the score. | | $2$ | $30$ | $1 \leq N \leq 1000$, $1 \leq M \leq 100$, at least one column contains only `*` | Each test point is scored independently. | | $3$ | $30$ | $1 \leq N \leq 100000$, $1 \leq M \leq 100000$, $M \times N \leq 100000$ | You must pass all test points in this subtask to get the score. | Translated by ChatGPT 5