题目描述

初始时，在一个 $n\times n$ 的棋盘上，有 $m$ 个细菌，第 $i$ 个细菌在第 $x_i$ 行第 $y_i$ 列。

细菌繁殖速度很快，每秒会分别向上下左右一个方格繁殖一个细菌。请输出 $t$ 秒后，棋盘上每个格子是否有细菌，如果有则输出 $1$，否则输出 $0$。

输入格式

第一行，包含三个整数 $n,m,t$；

接下来 $m$ 行，每行包括两个整数，$x_i,y_i$。

输出格式

共 $n$ 行，每行包括 $n$ 个整数，整数和整数之间用一个空格隔开。

输入输出样例 #1

输入 #1

7 2 2
7 6
2 2

输出 #1

1 1 1 0 0 0 0 
1 1 1 1 0 0 0 
1 1 1 0 0 0 0 
0 1 0 0 0 0 0 
0 0 0 0 0 1 0 
0 0 0 0 1 1 1 
0 0 0 1 1 1 1

输入输出样例 #2

输入 #2

10 3 3
7 5
5 5
6 6

输出 #2

0 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
0 0 0 1 1 1 0 0 0 0 
0 0 1 1 1 1 1 0 0 0 
0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 1 1 0 
0 1 1 1 1 1 1 1 0 0 
0 0 1 1 1 1 1 0 0 0 
0 0 0 1 1 1 0 0 0 0 
0 0 0 0 1 0 0 0 0 0

说明/提示

数据范围：

对于 $10\%$ 的数据，$t=0$；

对于 $20\%$ 的数据，$1\le n\le 50$，$m=1$；

对于 $50\%$ 的数据，$1\le n\le 50$，$0\le t\le 10$；

对于 $80\%$ 的数据，$1\le n\le 500$，$0\le t\le 100$；

对于 $100\%$ 的数据，$1\le n\le 1000$，$0\le t\le 10^9$，$1\le m\le 20$。