Семен и Антисемен играют в игру. Изначально каждому игроку дано одно фиксированное целое положительное число, которое не меняется в процессе игры. Семену дано число a, Антисемену дано число b. Также у них есть кучка из n камней. Игроки ходят по очереди, первый ход делает Семен. На своем ходу игрок должен взять из кучки число камней, равное наибольшему общему делителю данного ему числа и количества оставшихся камней в кучке. Проигрывает тот, кто не сможет взять требуемое число камней (по причине того, что в кучке остается строго меньше камней, чем нужно взять).
Ваша задача — по заданным a, b и n определить, кто выиграет в этой игре.
Выходные данные
Если выиграет Семен, выведите «0» (без кавычек), иначе выведите «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 четное, последний камень возьмет Антисемен, а Семен после этого не сможет сделать ход.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 9
|
0
|
|
2
|
1 1 100
|
1
|