题目描述

众所周知，2012 年人类对古代历法格外关注。尤其令人感兴趣的是那些并不会在 2012 年终结的古代历法。

鞑靼斯坦的考古学家在这一方向上有了惊人的发现：他们在古代墓葬中发现了一块长方形石板。经过对残存符号的破译，石板被记成一个表格，共有 $N$ 行，每行包含 $M$ 个十进制数字。

但石板并没有被完全破译，因为有些数字已经磨损消失。表格中丢失的数字用字符 * 表示。

考古学家认为，这块石板记录的是一种古代日历。表格中的每一行都是一个 $M$ 位的日期编号，并且这些编号表示某段连续时期中的连续日期：

• 第一行表示该时期的第一天编号；
• 从第二行开始，每一行的编号都比上一行大 $1$；
• 该日历没有世界末日：在编号为 $M$ 个 9 的那一天之后，下一天的编号为 $M$ 个 0。

请编写程序，补全所有缺失数字，使得从第二行开始，每一行都恰好比上一行大 $1$（按 $10^M$ 取模），并输出找到的日历中第一天的编号。

输入格式

第一行包含两个整数 $N,M$，分别表示表格行数和每个编号的长度。

接下来 $N$ 行，每行包含 $M$ 个字符，每个字符为十进制数字 0 到 9 或 *。

数据范围：

$$1 \le N \le 100000,\qquad 1 \le M \le 100000,\qquad N\times M \le 100000.$$

输出格式

输出一行，包含 $M$ 个数字，表示日历中第一天的编号。

如果有多种补全方式，输出任意一种即可。保证至少存在一种合法补全方式。

样例

样例 1

1 2
23

23

样例 2

3 3
1**
*1*
**1

109

样例 3

2 3
9**
00*

999

样例 4

3 4
****
*0**
01**

0098

子任务与评分

子任务	分值	限制
1	40	$1 \le N \le 1000,\ 1 \le M \le 100$；每一列至少有一个已知数字
2	30	$1 \le N \le 1000,\ 1 \le M \le 100$；至少有一列全为 *，每个测试点单独计分
3		$1 \le N \le 100000,\ 1 \le M \le 100000,\ N\times M \le 100000$