A. Эпическая игра
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Семен и Антисемен играют в игру. Изначально каждому игроку дано одно фиксированное целое положительное число, которое не меняется в процессе игры. Семену дано число a, Антисемену дано число b. Также у них есть кучка из n камней. Игроки ходят по очереди, первый ход делает Семен. На своем ходу игрок должен взять из кучки число камней, равное наибольшему общему делителю данного ему числа и количества оставшихся камней в кучке. Проигрывает тот, кто не сможет взять требуемое число камней (по причине того, что в кучке остается строго меньше камней, чем нужно взять).

Ваша задача — по заданным a, b и n определить, кто выиграет в этой игре.

Входные данные

В единственной строке через пробел записаны целые числа a, b и n (1 ≤ a, b, n ≤ 100) — числа, данные Семену и Антисемену соответственно, и исходное количество камней в кучке.

Выходные данные

Если выиграет Семен, выведите «0» (без кавычек), иначе выведите «1» (без кавычек).

Примеры
Входные данные
3 5 9
Выходные данные
0
Входные данные
1 1 100
Выходные данные
1
Примечание

Наибольшим общим делителем двух неотрицательных целых чисел a и b называется такое наибольшее положительное целое число k, что a делится на k без остатка, и, аналогично, b делится на k без остатка. Обозначим через gcd(a, b) операцию вычисления наибольшего общего делителя чисел a и b. В частности, gcd(x, 0) = gcd(0, x) = x.

В первом примере игра будет идти следующим образом:

  • Семен должен взять из кучки gcd(3, 9) = 3 камня. После его хода в кучке остается 6 камней.
  • Антисемен должен взять из кучки gcd(5, 6) = 1 камень. После его хода в кучке остается 5 камней.
  • Семен должен взять из кучки gcd(3, 5) = 1 камень. После его хода в кучке остается 4 камня.
  • Антисемен должен взять из кучки gcd(5, 4) = 1 камня. После его хода в кучке остается 3 камня.
  • Семен должен взять из кучки gcd(3, 3) = 3 камня. После его хода в кучке остается 0 камней.
  • Антисемен должен взять из кучки gcd(5, 0) = 5 камня. Так как 0 < 5, это сделать невозможно, и Антисемен проигрывает.

Во втором примере каждый игрок на каждом ходу берет из кучки по одному камню. Так как n четное, последний камень возьмет Антисемен, а Семен после этого не сможет сделать ход.