P15297 [ROI 2012 Day 1] calendar 古代日历

翻译来源：[loj #5458. 「ROI 2012 Day 1」古代日历](https://loj.ac/p/5458)。

众所周知，2012 年人类对古代日历表现出了极大的关注。尤其令人感兴趣的是那些并未在 2012 年结束的日历。鞑靼斯坦的考古学家在这方面取得了惊人的发现。他们在古代墓葬中发现了一块矩形石板，经过破译保存下来的符号后，将其记录为一个包含 $N$ 行、每行 $M$ 个十进制数字的表格。然而，石板未能完全破译，因为部分数字已经磨损。表格中丢失的数字用符号 `*` 替代。 考古学家认为，这块石板是一个古代日历，其中的 $M$ 位数字表示某个时间段内连续的日子编号。第一个数字是该时间段第一天的编号，随后每个数字比前一个数字大 $1$。根据这个日历，世界末日并不存在，在由 $M$ 个 $9$ 组成的日子编号之后，紧接着的是由 $M$ 个 $0$ 组成的日子编号。 你需要编写一个程序，恢复丢失的数字，使得表格中从第二行开始的每个数字比前一行大 $1$，并输出找到的日历中第一天的编号。

输入文件的第一行包含两个自然数 $N$ 和 $M$ $(1 \leq N \leq 100000, 1 \leq M \leq 100000, M \times N \leq 100000)$，分别表示表格的行数和每行的长度。 接下来有 $N$ 行，每行包含 $M$ 个字符，仅由十进制数字 $0$ 到 $9$ 和符号 `*` 组成。

输出文件应包含一行，由 $M$ 个数字组成，表示日历中第一天的编号。如果存在多种恢复方式，可以输出任意一种。保证至少存在一种恢复方式。

详细子任务附加限制及分值如下表所示： | 子任务 | 分值 | 附加限制 | 说明 | | :----: | :--: | :-----------------------------------: | :-----------------------------------------------: | | $1$ | $40$ | $1 \leq N \leq 1000$，$1 \leq M \leq 100$，每列至少有一个保存下来的数字 | 需通过该子任务所有测试点才可获得分数 | | $2$ | $30$ | $1 \leq N \leq 1000$，$1 \leq M \leq 100$，至少有一列只包含`*` | 每个测试点独立评分 | | $3$ | $30$ | $1 \leq N \leq 100000$，$1 \leq M \leq 100000$，$M \times N \leq 100000$ | 需通过该子任务所有测试点才可获得分数 |