>土地分割

ハウジングメーカーの山田ハウスは、新たな目玉商品として、学校や病院など環境が充実している緑ホームタウンの分譲地を売り出しました。この分譲地は複数の区画に分割されており、好きなだけ購入できますが、購入する区画を合わせた土地の形状は長方形(正方形を含む)でなければなりません。

山田ハウスは、全区画が完売した分譲地を管理するため購入者ごとに境界線を引き、その区画の 1つに購入者番号を書いた看板を設置しておきました。境界線は地面に木の枝で線を引いただけのものであったため、数日後の豪雨により消えてしまい看板だけが残りました。図 1 は看板のあった区画に、その区画を買った購入者番号を記したものです。これでは分譲地がどのように買われたか分かりません。救いは事務所の引き出しにあった購入者番号 b と購入区画数 k のメモ(図 2)が見つかったことです。

図１（左）：看板の配置、図2（右）：メモ

プログラマーであるあなたは、プログラムを書いて山田ハウスを助けることになりました。分譲地の大きさ X × Y 、購入者数 n 、メモの情報 b、 k 、及び看板の位置情報 s を入力とし、図 3 に示すように各区画の購入者を出力するプログラムを作成してください。

図3：各区画の購入者

与えられた情報について、以下の場合は NA と出力します。

• 区画を区別する方法が存在しない場合
• 区画を区別する方法が複数存在する場合

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロが３つの行で示されます。各データセットは以下の形式で与えられます。

X Y n
b1 k1
b2 k2
:
bn kn
s11 s21 ... sX1
s12 s22 ... sX2
:
s1Y s2Y ... sXY

1 行目にX, Y, n (1 ≤ X, Y ≤ 10, 1 ≤ n ≤ 15) が与えられます。続く n 行にメモの i 行目に書かれた情報 b_i (1 ≤ b_i ≤ n), k_i (1 ≤ k_i ≤ 100) が与えられます。

続く Y 行に区画情報の i 行目の情報 s_ij が与えられます。s_ij はi 行目の左から j 番目の区画の看板情報を表します。看板の情報 s_ij として、その区画に看板が無い場合は 0 、看板がある場合はその区画の購入者番号が与えられます。

データセットの数は 50 を超えません。

Output

入力データセットごとに、購入者情報またはNA を出力します。

Sample Input

5 4 6
1 6
2 4
3 3
4 4
5 1
6 2
0 0 1 0 0
0 0 0 2 0
0 0 0 3 0
0 4 5 0 6
3 3 1
1 9
0 0 1
0 0 0
0 0 0
4 4 4
1 6
2 2
3 4
4 4
0 1 0 0
0 0 0 2
0 0 3 0
0 4 0 0
0 0 0

Output for the Sample Input

1 1 1 2 2
1 1 1 2 2
4 4 3 3 3
4 4 5 6 6
1 1 1
1 1 1
1 1 1
NA

---