KUPCオンサイト京都会場である総合研究7号館は、各階に談話室が設けられている。 室内には大きなホワイトボードとプロジェクタとスクリーン、きれいな机と椅子が設置されていて、基本的に誰でも自由に使うことができる。 談話室に集まってプログラミングコンテストに参加する人たちもいて、7号館の住人は何かとお世話になっている部屋である。

今日は談話室で、京子さんと結衣さんの2人が、相性度を測るために占いをしている。 この占いでは長さ N,M の2つの数列 A=(a_1,...,a_N) と B=(b_1,...,b_M) を使う。 占いは以下の手順で行われる。

1. 京子さんと結衣さんの間で2つの整数 N,M を決めた後、Q 個の約束をする。各約束は2つの整数 c_i,d_i で表され、数列 A の c_i 番目の数字と数列 B の d_i 番目の数字が同じでなければならないことを指す。約束を一つでも破ってしまったら、二人の相性度は0となる。
2. 京子さんは長さ N の数列 A=(a_1,...,a_N) をひとつ頭の中に思い浮かべる。同様に、結衣さんは長さ M の数列 B=(b_1,...,b_M) をひとつ頭の中に思い浮かべる。
3. 京子さんと結衣さんは、それぞれ自分の思い浮かべた数列の数字を繰り返しホワイトボードに書いていく。より厳密には、i(≥1) 回目の書き込みで、京子さんは数列 A の ((i-1) mod N)+ 1 番目の数字を、結衣さんは数列 B の ((i-1) mod M)+ 1 番目の数字を、同時にホワイトボードに書く。x mod y は x を y で割った余りを指す。t 回目の書き込みで、二人が同時に書いた数字が異なる場合、相性占いを終了し、二人の相性度は t となる。
4. 手順3が 10^{10} 回以上続いてしまうと、結衣さんは占いに飽きてしまい、二人の相性度は0となる。

京子さんはたった今、結衣さんと Q 個の約束をしたところである。京子さんは今からしようとしている占いで最大いくつの相性度を得られるのか非常に気にしているので、談話室にいたあなたは相性の最大値を計算してあげることにした。

N M Q
c_1 d_1
…
c_Q d_Q

入出力例

入力例1

3 2 0

出力例1

4

入力例2

3 6 0

出力例2

6

入力例3

3 2 1
3 2

出力例3

3

入力例4

3 3 2
1 3
3 1

出力例4

2

入力例5

4 4 3
1 4
3 4
4 4

出力例5

3