Migrated from Lutece 2700 Squad 404

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In a war-torn world, the order of human society has been severely disrupted. As a commander of Squad 404, which specializes in covert operations and electronic warfare, you need to make combat preparations.

The battlefield can be seen as a grid with $n$ rows and $m$ columns of cells. The rows are numbered from $0$ to $n-1$, and the columns are numbered from $0$ to $m-1$. We can use $(x,y)$ to indicate a cell in row $x$ and column $y$.

The rule of moving on the battlefield is special. If someone passes through the left border, he will be teleported to the right border, and vice versa, as well as the top and bottom borders. Squad 404 moves a fixed distance in each step. Formally, they can make four kinds of moves in each step:

• Move upper-left: from $(x,y)$ to $((x-a+n)\bmod n,(y-b+m)\bmod m)$
• Move upper-right: from $(x,y)$ to $((x-a+n)\bmod n,(y+b)\bmod m)$
• Move lower-left: from $(x,y)$ to $((x+a)\bmod n,(y-b+m)\bmod m)$
• Move lower-right: from $(x,y)$ to $((x+a)\bmod n,(y+b)\bmod m)$

Here $a \bmod b$ means the remainder of $a$ divided by $b$. For example, $7 \bmod 3=1$, since $7\div 3=2\cdots1$.

If Squad 404 starts from $(0,0)$, please calculate how many different cells they can reach.

Input

The first line contains two integers $n,m$ ($1 \le n,m \le 10^9$), indicating the number of rows and columns of the grid.

The second line contains two integers $a,b$ ($0 \le a \le \min(n-1,10^6)$, $0 \le b \le \min(m-1,10^6)$, $a+b\neq 0$), indicating the fixed distance in each step.

Output

Print an integer, indicating the number of different cells they can reach.

Samples

10 1
6 0

5

4 4
1 3

8

6 2
4 1

6

Note

For the first example, they can reach a total of $5$ cells $(0,0),(2,0),(4,0),(6,0),(8,0)$.

For the second example, they can reach a total of $8$ cells $(0,0),(0,2),(1,1),(1,3),(2,0),(2,2),(3,1),(3,3)$.

For the third example, they can reach a total of $6$ cells $(0,0),(2,0),(4,0),(0,1),(2,1),(4,1)$.

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛