시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 299 45 34 20.859%

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 2개로 시작한다.

동혁이와 동규는 유클리드 게임을 하려고 한다. 동혁이가 먼저 시작한다. 동혁이는 큰 수를 작은 수의 배수만큼 뺀다. 이 때, 큰 수는 음이 아닌 정수가 되어야 한다. 

그런 다음 동규는 동혁이가 한 것과 똑같이 큰 수를 작은 수의 배수만큼 뺀다. 이런식으로 두 플레이어는 서로 번갈아가면서 게임을 한다. 이 때, 큰 수를 0으로 만든 사람이 게임을 승리하게 된다.

예를 들어, 다음과 같이 (25, 7)로 시작한 게임을 생각해보자.

25 7

11 7

4 7

4 3

1 3

1 0

위와 같이 게임을 하게 되면, 동혁이가이기게 된다. (큰 수와 작은 수는 각 턴에서 큰 수와 작은 수이다.)

시작하는 두 자연수가 주어졌을 때, 두 플레이어가 최적의 방법으로 게임을 할 때, 누가 이기는지 구하는 프로그램을 작성하시오.

입력

입력은 여러 줄로 이루어져 있다. 각 줄은 게임을 시작하는 두 숫자이다. 항상 동혁이가 먼저 게임을 시작한다. 두 자연수는 231-1보다 작거나 같다. 입력의 마지막 줄에는 0 두 개가 주어진다.

출력

각 입력에 대해서 동혁이가 이기면 A wins를, 동규가 이기면 B wins를 출력한다.

예제 입력

34 12
15 24
0 0

예제 출력

A wins
B wins

힌트