时间限制:1000ms  空间限制:256MB

题目描述

扫雷游戏完成后会显示一幅图，图中标示了每个格子的地雷情况。现在，一个 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，并确保所有地雷位置不重复。