H: ジャンプパーティ

問題

とあるダンスホールで $N$ 人の参加するダンスパーティーが行われる。 そのダンスホールは縦方向に $H$ 個、横方向に $W$ 個のグリッドに分けられており、 左上を $(0,0)$、上から $r$ マス、左から $c$ マス目のグリッドの座標を $(r,c)$ と表す。 $i$ 番目の参加者の初期位置は $(R_i, C_i)$ であり、$(i,j)$ のグリッドには $(r_{ij}, c_{ij})$ が書かれている。

各参加者は、無限に続く音楽に合わせて次のように同時に移動を行う。

• その時にいる座標が $(i,j)$ のとき、$(r_{ij}, c_{ij})$ へジャンプで移動する。

それぞれのグリッドは狭く、2 人以上の参加者が同時に同じグリッドに移動すると衝突してしまう。ただし、空中で衝突することは無いとする。 これを聞いたあなたは、ジャンプ後に 2 人以上の参加者が衝突してしまわないかと心配になった。 そこで、衝突が起こる可能性があるか、あるならば何回目のジャンプの後に衝突が起こるかを求めることにした。

制約

• $1 \le H,W \le 500$
• $0 \le N \le H \times W$
• $0 \le r_{ij} < H \ (0 \le i < H, 0 \le j < W)$
• $0 \le c_{ij} < W \ (0 \le i < H, 0 \le j < W)$
• $0 \le R_i < H \ (0 \le i < N)$
• $0 \le C_i < W \ (0 \le i < N)$
• 参加者の初期位置は相異なる

入力形式

入力は以下の形式で与えられる。

$H \ W \ N$
$r_{00} \ c_{00} \ \cdots \ r_{0 \ W-1} \ c_{0 \ W-1}$
$\vdots$
$r_{H-1 \ 0} \ c_{H-1 \ 0} \ \cdots \ r_{H-1 \ W-1} \ c_{H-1 \ W-1}$
$R_0 \ C_0$
$\vdots$
$R_{N-1} \ C_{N-1}$

この問題では入力ファイルが非常に大きくなることがあることに注意せよ。 C++ ならこのページを参考にすると良いかもしれない。

出力

衝突が起こる場合は何回目のジャンプの後に起こるかを 1 行で出力せよ。 そうでない場合は -1 を出力せよ。 また、末尾に改行を出力せよ。

サンプル

サンプル入力 1

2 2 2
1 0 0 1
0 0 1 0
0 0
0 1

サンプル出力 1

-1

サンプル入力 2

2 2 2
1 0 0 1
0 0 1 0
0 0
1 1

サンプル出力 2

1