题目描述

在一个 $n \times m$ 的网格中，每个网格要么有一定数量的杂草，要么是一块石头（用-1表示）， 定义一个网格 （x，y） 的生草程度为与其相邻的9宫格的杂草总和（如果处于边界，则相邻网格数可能小于9），请你计算并返回给定网格的生草程度。

注意，如果 （x，y） 的位置是石头，则不需计算生草程度，输出时请用字符 '*' 代替。

由于结果可能很大，请将结果对 1e9+9 取模。

输入

第一行两个整数 n 和 m 接下来 n 行，每行 m 个数，表示（x，y）网格的杂草数量（用-1表示石头）

输出

一个 n $\times$ m 的矩阵

样例

3 3
1 -1 2
1 2 3
3 1 -1

4 * 7 
8 13 8 
7 10 *

数据说明

10 <= n,m <= 1000