给你一个二分图。左半部分包含 $n$ 个顶点，编号为 $0$ 到 $n - 1$；右半部分包含 $m$ 个顶点，编号为 $0$ 到 $m - 1$。初始时有 $k$ 条边。在第 $i$ 步（从第 $0$ 步开始计数），会在左半部分的顶点 $i \bmod n$ 与右半部分的顶点 $i \bmod m$ 之间添加一条边。

需要经过多少步，该图才会变得连通？

输入格式

第一行包含三个整数 $n$，$m$ 和 $k$（$1 \le n, m \le 10^9$，$0 \le k \le 10^5$）。

接下来的 $k$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示连接左半部分顶点 $u_i$ 和右半部分顶点 $v_i$ 的第 $i$ 条边（$0 \le u_i < n$，$0 \le v_i < m$）。

允许存在重边。

输出格式

输出该问题的答案。如果该图永远无法变得连通，则输出 -1。

样例

输入样例 1

3 5 2
1 3
2 1

输出样例 1

5

输入样例 2

3 3 1
0 2

输出样例 2

-1