Gridlandia 这个国家自然可以表示为一个房屋网格。

Gridlandia 计划在网格的某些点上安装若干个蜂窝基站。当居民连接蜂窝数据时，他们的手机会首先尝试连接到距离最近的基站，如果连接失败，则会尝试连接到距离第二近的基站。Gridlandia 政府担心某些基站的负载会比其他基站重得多。请通过计算每个房屋距离最近和第二近的基站来帮助他们，距离采用曼哈顿距离衡量，即行差的绝对值与列差的绝对值之和。

输入格式

第一行包含三个整数 $r, c$ ($1 \le r, c \le 500, r \cdot c \ge 2$) 和 $n$ ($2 \le n \le 2 \cdot 10^5$)，其中 Gridlandia 是一个 $r$ 行 $c$ 列的网格，$n$ 是基站的数量。基站编号从 $1$ 到 $n$。

接下来的 $n$ 行，每行包含两个整数 $i$ 和 $j$ ($1 \le i \le r, 1 \le j \le c$)，依次表示各基站的位置。每个 $(i, j)$ 坐标对都是唯一的。

输出格式

输出的前 $r$ 行，每行应包含 $c$ 个空格分隔的整数。第 $i$ 行第 $j$ 列的整数应为距离位置 $(i, j)$ 最近的基站编号（按曼哈顿距离计算）。

接下来的 $r$ 行，每行也应包含 $c$ 个空格分隔的整数。第 $i$ 行第 $j$ 列的整数应为距离位置 $(i, j)$ 第二近的基站编号（按曼哈顿距离计算）。

如果对于某个位置存在多个距离最近的基站，则输出编号最小的那一个。同样，如果存在多个距离第二近的基站，也输出编号最小的那一个。

样例

输入格式 1

4 8 3
1 1
4 1
2 6

输出格式 1

1 1 1 1 3 3 3 3
1 1 1 3 3 3 3 3
2 2 2 3 3 3 3 3
2 2 2 2 3 3 3 3
2 2 3 3 1 1 1 1
2 2 3 1 1 1 1 1
1 1 1 2 2 2 2 2
1 1 1 3 2 2 2 2