Ancient Calendar#3156
In 2012, there was heightened interest in ancient calendars, especially those that do not end in the year . Archaeologists in Tatarstan made a remarkable discovery: they found a rectangular tablet in ancient burials, which, after decoding the preserved symbols, was recorded as a table with rows, each containing decimal digits. However, some digits could not be deciphered because they had worn away, and the missing digits in the table were replaced by the symbol "*".
Researchers believe that this tablet is an ancient calendar, where each -digit number represents the sequence number of a day during a period. The first number is the first day's number, and each subsequent number is exactly one greater than the previous one. According to this calendar, there is no apocalypse: after the day denoted by nines, the next day is denoted by zeros.
You are required to write a program that reconstructs the missing digits in such a way that each number in the table, starting from the second row, is exactly one greater than the previous one. The program should output the number of the first day in the reconstructed calendar.
The first line contains the natural numbers and — the number of rows in the table and the length of each row (1 \leq N \leq 100000, 1 \leq M \leq 100000, M \times N \leq 100000). Then you are given rows of characters each, composed only of decimal digits from to and the symbol "*".
The output should be a single line of digits — the number of the first day of the calendar. If there are multiple possible reconstructions, you may output any of them. It is guaranteed that at least one reconstruction exists.
Example 1