D. Firewood
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Isaiah and Mina are camping and after a long foraging trip, they collected $$$n$$$ total pieces of firewood. However, they are each in a different camp-site and so they decide to place their stash in a central location. Additionally, Isaiah and Mina each have their own warming constants, denoted by $$$a$$$ and $$$b$$$ respectively. The warming constant is a fixed number such that the amount of firewood the person needs is equal to the greatest common divisor of the number of pieces of firewood left in the central stash and the person's warming constant.

Every night, Mina takes the amount of firewood she needs first and then Isaiah takes the quantity that he needs. Given this scenario, figure out the person who first does not have enough firewood to take from the stash (the number of pieces of firewood is strictly less than the amount that the person needs to take, note that for this problem we define $$$\gcd(0,x) = \gcd(x, 0) = x$$$).

Input

The first and only line of input will contain three space-separated integers $$$n$$$, $$$a$$$, and $$$b$$$ such that $$$1 \leq n, a, b \leq 10^{4}$$$ where $$$n$$$ is the number of pieces of firewood in the stash at the start, $$$a$$$ is the warming constant for Isaiah, and $$$b$$$ is the warming constant for Mina.

Output

If Isaiah will be the first one to not have enough firewood, output 0, otherwise output 1.

Examples
Input
9 5 3
Output
0
Input
12 4 2
Output
1
Note

In the first sample, Mina will start and take $$$\gcd(9,3) = 3$$$ pieces, leaving $$$6$$$ in the stash. Then Isaiah will take $$$\gcd(6,5) = 1$$$ piece, leaving $$$5$$$ in the stash. Mina will then take $$$\gcd(5, 3) = 1$$$ piece, leaving $$$4$$$ in the stash. Isaiah will take $$$\gcd(4,5) = 1$$$ piece, leaving $$$3$$$ in the stash. Mina will take $$$\gcd(3,3) = 3$$$ pieces, leaving $$$0$$$ in the stash. Now, when Isaiah goes to take $$$\gcd(0, 5) = 5$$$ pieces, there will not be enough for him so you output 0.