JYY recently obtained a magic book from a friend and is now practicing the JSOI magic within it.

The JSOI magic casting process is as follows: there is a bipartite graph with $N$ nodes on the left and $M$ nodes on the right. The $N$ nodes on the left are labeled from $0$ to $N-1$, and the $M$ nodes on the right are labeled from $0$ to $M-1$. Initially, this bipartite graph already has $K$ connections (each connection corresponds to an undirected edge in the bipartite graph).

The casting process consists of several rounds, numbered starting from $0$. In the $i$-th round, a connection is added between the node labeled $i \pmod N$ on the left and the node labeled $i \pmod M$ on the right. This process continues until all nodes in the bipartite graph are connected (i.e., the bipartite graph becomes connected). At this point, the magic circle is activated, and JSOI will give you a cute Accept!

JYY wants to know the number of rounds (i.e., the number of added edges) required to activate the magic circle given the initial conditions.

Input

The first line contains three positive integers $N$, $M$, and $K$, representing the number of nodes on the left side, the number of nodes on the right side, and the number of initial edges, respectively.

The next $K$ lines each contain two integers $u_i$ and $v_i$, representing an initial connection between node $u_i$ on the left and node $v_i$ on the right.

Output

Output a single integer representing the total number of rounds performed. JSOI guarantees that the magic circle can always be activated.

Constraints

• For 20% of the data, $N, M \le 10^5$;
• For another 20% of the data, $K = 0$;
• For 100% of the data, $1 \le N, M \le 10^9$, $0 \le K \le 10,000$.

Examples

Input 1

3 5 2
1 3
2 0

Output 1

5