西蒙和安蒂西蒙玩游戏。最初,每个玩家都会收到一个固定的正整数,该整数在整个游戏过程中不会改变。 Simon 收到号码 a,Antisimon 收到号码 b。他们还有一堆n块石头。队员们轮流行动,西蒙开始行动。在移动过程中,玩家从堆中取出的石子数量应等于他收到的固定数量与堆中剩余石子数量的最大公约数。当玩家无法取出所需数量的石子时(即堆中剩余的石子严格少于需要取出的石子),玩家就输了。
你的任务是根据给定的 a、b 和 n 确定谁赢得了比赛。
输入
唯一的字符串包含空格分隔的整数 a、b 和 n (1 ≤ a, b, n ≤ 100) — Simon 和 Antisimon 相应收到的固定数字以及堆中石子的初始数量。
输出
如果 Simon 获胜,则打印“0”(不带引号),否则打印“1”(不带引号)。
示例
输入 #1
3 5 9
输出 #1
0
输入 #2
1 1 100
输出 #2
1
注意
两个非负整数a和b的最大公约数是最大正整数k,使得a可以被k整除而没有余数,同样,b可以被k整除而没有余数。令gcd(a, b)表示计算数字a和b的最大公约数的操作。具体来说,gcd(x, 0) = gcd(0, x) = x。
在第一个示例中,游戏将如下所示:
- Simon 应该从堆中取出 gcd(3, 9) = 3 个石头。在他移动之后,堆里还剩下 6 个石子。
- Antisimon 应该从堆中取出 gcd(5, 6) = 1 块石头。在他移动之后,堆里还剩下 5 个石子。
- Simon 应该从堆中取出 gcd(3, 5) = 1 块石头。在他移动之后,堆里还剩下 4 个石子。
- Antisimon 应该从堆中取出 gcd(5, 4) = 1 块石头。在他移动之后,堆里还剩下 3 个石子。
- Simon 应该从堆中取出 gcd(3, 3) = 3 个石头。在他移动之后,堆中剩下 0 个石子。
- Antisimon 应该从堆中取出 gcd(5, 0) = 5 颗石头。当 0 < 5 时,这是不可能的,Antisimon 输了。
在第二个示例中,每个玩家在每次移动过程中都会从堆中取出一颗石头。由于 n 是偶数,安提西蒙拿走了最后一块石头,之后西蒙就无法再采取行动了。