幾何割当制

$N \times M$ のグリッドがある。各マスは空きマスまたは障害物マスである。

グリッドの左下の頂点を $(0,0)$、右上の頂点を $(M,N)$ とする。すべての格子点の座標は整数である。

$Q$ 個のクエリが与えられる。各クエリでは、互いに異なる 2 つの格子点 $(x_1,y_1)$ と $(x_2,y_2)$ が与えられる。

2 点を結ぶ線分が内部を通過する障害物マスの個数を求めよ。線分が障害物マスの辺や頂点に触れるだけで、そのマスの内部を通過しない場合、そのマスは数えない。

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

$N\ M\ Q$ $S_1$ $S_2$

各クエリについて、線分が内部を通過する障害物マスの個数を 1 行に出力せよ。

• $1 \le NM \le 200\,000$.
• $1 \le Q \le 200\,000$.
• $$ は , のみからなる長さ の文字列である。()