Minesweeper

Problem Description

Xiaoyang is playing the classic game "Minesweeper" and wants to generate a Minesweeper map himself.

Xiaoyang wants a map of $n$ rows and $m$ columns, with $n \times m$ cells in total. The rows are numbered $1, 2, \dots, n$ and the columns $1, 2, \dots, m$. Some cells are mines; the others are not.

Xiaoyang designates $q$ cells as mines, and all other cells are non-mines. He wants you to compute, for each non-mine cell, how many mine cells it is adjacent to.

Two cells are adjacent if and only if they share at least one vertex (that is, for a cell not on the map's edge, the $8$ surrounding cells are all adjacent to it).

Input Format

The input contains $q + 1$ lines. The first line contains three positive integers $n$, $m$, and $q$: the number of rows, the number of columns, and the number of mines. The following $q$ lines each contain two integers: the row and column of the $i$-th mine. The given mines are guaranteed to be distinct.

Output Format

Output $n$ lines, each with $m$ characters separated by spaces. For cell $(i, j)$, output:

1. * if it is a mine;
2. otherwise the number of adjacent mines (a digit from 0 to 8).

Sample Input

3 4 4
1 1
1 3
2 4
3 2

Sample Output

* 2 * 2
2 3 3 *
1 * 2 1

Sample Explanation

From the input, the map is $3$ rows and $4$ columns with $4$ mines at $(1,1)$, $(1,3)$, $(2,4)$, and $(3,2)$. In the output * marks a mine; the other digits mark how many mines each non-mine cell is adjacent to. For example, cell $(2,2)$ (non-mine) is adjacent to three mines $(1,1)$, $(1,3)$, and $(3,2)$, so it outputs $3$; cell $(1,2)$ is adjacent to two mines $(1,1)$ and $(1,3)$, so it outputs $2$. The rest follow the same rule, giving the sample output.

Constraints

• $3 \le n, m \le 500$
• $1 \le q \le n \cdot m$
• The given mines are inside the map and distinct; rows and columns are $1$-indexed.