[119A] Juego Épico

Enlace a Codeforces

Simón y Antisimón juegan un juego. En un inicio cada jugador recibe un entero positivo fijo que no cambia a través del juego. Simón recibe el número $a$ y Antisimón el número $b$. También tienen un montón de $n$ piedras. Los jugadores hacen movimientos por turnos y Simón empieza. Durante un movimiento, un jugador debe retirar del montón una cantidad de piedras igual al máximo común divisor entre el número que ha recibido y el número de piedras que quedan en el montón. Un jugador pierde cuando no puede tomar la cantidad requerida de piedras (es decir, cuando el montón tiene estrictamente menos piedras que las que uno necesita tomar).

Tu tarea es determinar quién gana el juego con unos valores $a$, $b$ y $n$ determinados.

Entrada

Una línea con tres números $a$, $b$ y $n$ separados por espacio ($1 \leq a, b, n \leq 100$) - los números fijos que han recibido Simón y Antisimón y la cantidad inicial de piedras en el montón.

Salida

Si Simón gana, imprime "0" (sin las comillas), de otro modo imprime "1" (sin las comillas).

Ejemplos

input:
3 5 9

output:
0

input:
1 1 100

output:
1

Nota

El máximo común divisor entre dos enteros positivos $a$ y $b$ es el mayor entero positivo $k$, tal que $a$ sea divisible por $k$ sin resto y de modo similar, que $b$ sea divisible por $k$ sin resto. $mcd(a, b)$ representa la operación de calcular el máximo común divisor para los números $a$ y $b$. Específicamente, $mcd(x, 0) = mcd(0, x) = x$.

En el primer ejemplo el juego irá de este modo:

• Simón debería tomar $mcd(3, 9) = 3$ piedras del montón. Luego de su movimiento, quedarán 6 piedras.

• Antisimón debería tomar $mcd(5, 6) = 1$ piedra del montón. Luego de su movimiento, quedarán 5 piedras.

• Simón debería tomar $mcd(3, 5) = 1$ piedra del montón. Luego de su movimiento, quedarán 4 piedras.

• Antisimón debería tomar $mcd(5, 4) = 1$ piedra del montón. Luego de su movimiento, quedarán 3 piedras.

• Simón debería tomar $mcd(3, 3) = 3$ piedras del montón. Luego de su movimiento, quedarán 0 piedras.

• Antisimón debería tomar $mcd(5, 0) = 5$ piedras del montón. Como $0 < 5$, es imposible y Antisimón pierde.

En el segundo ejemplo cada jugador toma una piedra cada movimiento. Como $n$ es par, Antisimón toma la última piedra y Simón no puede hacer su movimiento después de eso.