Gridlandiaという国は、当然ながら、住宅のグリッドとして表現できる。

Gridlandiaでは、グリッド上のいくつかの地点に複数の携帯電話基地局を設置する計画がある。住民が携帯電話のデータ通信に接続する際、電話はまず最も近い基地局に接続を試み、それが失敗した場合は2番目に近い基地局に接続する。Gridlandia政府は、一部の基地局が他の基地局よりもはるかに過負荷になることを懸念している。各住宅について、マンハッタン距離（行の差と列の差の合計）で測定した、最も近い基地局と2番目に近い基地局の両方を計算することで、彼らを支援せよ。

入力

入力の最初の行には、3つの整数 $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$ 行の各行には、基地局の位置を示す2つの整数 $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)$ に2番目に近い基地局の番号であるべきである。

ある位置に対して最も近い基地局が複数ある場合は、番号が最も小さいものを出力せよ。同様に、ある位置に対して2番目に近い基地局が複数ある場合も、番号が最も小さいものを出力せよ。

入出力例

入力 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