题目描述

扫雷游戏完成后会显示一幅图，图中标示了每个格子的地雷情况。现在，一个n * n方阵中有k个地雷，请你输出它的扫雷完成图。

输入格式

输入共k+1行：

第1行为2个整数n、k，用一个空格隔开，表示扫雷图方阵的规模和地雷的总数。

接下来k行，每行2个整数，表示一个地雷的行、列坐标。

输出格式

输出共n行，每行连续n个字符，每个字符对应扫雷完成图的一个格子。字符内容定义如下：

1、若该位置对应的格子是地雷，则输出“*”（英文星号）；
2、若该位置对应的格子不是地雷，其相邻格（指环绕它的左上、上、右上、右、右下、下、左下、左，共8个格子）有地雷，则输出相邻格地雷总数；
3、若该位置对应的格子不是地雷，其相邻格也没有地雷，则输出空格。

样例数据

输入样例1

9 5
2 7
3 7
8 9
9 9
3 5

输出样例1

     111 
   113*2 
   1*3*2 
   11211 


       11
       2*
       2*

数据规模与约定

对于20%的数据：n ≤ 10，k ≤ 10；

对于60%的数据：n ≤ 20，k ≤ 100；

对于100%的数据：n ≤ 30，k ≤ 150，并确保所有地雷位置不重复。

时间限制：$1 text {s}$

空间限制：$256 text {MB}$