시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 377 65 50 22.422%

문제

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

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

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

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

25 7

11 7

4 7

4 3

1 3

1 0

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

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

입력

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

출력

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

예제 입력 1

34 12
15 24
0 0

예제 출력 1

A wins
B wins

힌트

W3sicHJvYmxlbV9pZCI6IjQzNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWM3MjBcdWQwNzRcdWI5YWNcdWI0ZGMgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWJhODVcdWM3NzRcdWMxMWMgXHVkNTU4XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc3NFx1YWNlMCwgXHVjNzkwXHVjNWYwXHVjMjE4IDJcdWFjMWNcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWM2NDAgXHViM2Q5XHVhZGRjXHViMjk0IFx1YzcyMFx1ZDA3NFx1YjlhY1x1YjRkYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVkMDcwIFx1YzIxOFx1YjI5NCBcdWM3NGNcdWM3NzQgXHVjNTQ0XHViMmNjIFx1YzgxNVx1YzIxOFx1YWMwMCBcdWI0MThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcbjxwPlxyXG5cdFx1YWRmOFx1YjdmMCBcdWIyZTRcdWM3NGMgXHViM2Q5XHVhZGRjXHViMjk0IFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YWMwMCBcdWQ1NWMgXHVhYzgzXHVhY2ZjIFx1YjYxMVx1YWMxOVx1Yzc3NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViN2YwXHVjMmRkXHVjNzNjXHViODVjIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWIyOTQgXHVjMTFjXHViODVjIFx1YmM4OFx1YWMwOFx1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWQwNzAgXHVjMjE4XHViOTdjIDBcdWM3M2NcdWI4NWMgXHViOWNjXHViNGUwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmI5XHViOWFjXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCAoMjUsIDcpXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMGRkXHVhYzAxXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cclxuXHQyNSA3PFwvcD5cclxuPHA+XHJcblx0MTEgNzxcL3A+XHJcbjxwPlxyXG5cdDQgNzxcL3A+XHJcbjxwPlxyXG5cdDQgMzxcL3A+XHJcbjxwPlxyXG5cdDEgMzxcL3A+XHJcbjxwPlxyXG5cdDEgMDxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjOGMgXHViNDE4XHViYTc0LCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDBcdWM3NzRcdWFlMzBcdWFjOGMgXHViNDFjXHViMmU0LiAoXHVkMDcwIFx1YzIxOFx1YzY0MCBcdWM3OTFcdWM3NDAgXHVjMjE4XHViMjk0IFx1YWMwMSBcdWQxMzRcdWM1ZDBcdWMxMWMgXHVkMDcwIFx1YzIxOFx1YzY0MCBcdWM3OTFcdWM3NDAgXHVjMjE4XHVjNzc0XHViMmU0Lik8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViNDUwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NjAgXHViNTRjLCBcdWIyMDRcdWFjMDAgXHVjNzc0XHVhZTMwXHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IFx1YjQ1MCBcdWMyMmJcdWM3OTBcdWM3NzRcdWIyZTQuIFx1ZDU2ZFx1YzBjMSBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHViYTNjXHVjODAwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjQ1MCBcdWM3OTBcdWM1ZjBcdWMyMThcdWIyOTQgMjxzdXA+MzE8XC9zdXA+LTFcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMCBcdWI0NTAgXHVhYzFjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWIzZDlcdWQ2MDFcdWM3NzRcdWFjMDAgXHVjNzc0XHVhZTMwXHViYTc0IEEgd2luc1x1Yjk3YywgXHViM2Q5XHVhZGRjXHVhYzAwIFx1Yzc3NFx1YWUzMFx1YmE3NCBCIHdpbnNcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQzNDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFdWNsaWQncyBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5Ud28gcGxheWVycywgU3RhbiBhbmQgT2xsaWUsIHBsYXksIHN0YXJ0aW5nIHdpdGggdHdvIG5hdHVyYWwgbnVtYmVycy4gU3RhbiwgdGhlIGZpcnN0IHBsYXllciwgc3VidHJhY3RzIGFueSBwb3NpdGl2ZSBtdWx0aXBsZSBvZiB0aGUgbGVzc2VyIG9mIHRoZSB0d28gbnVtYmVycyBmcm9tIHRoZSBncmVhdGVyIG9mIHRoZSB0d28gbnVtYmVycywgcHJvdmlkZWQgdGhhdCB0aGUgcmVzdWx0aW5nIG51bWJlciBtdXN0IGJlIG5vbm5lZ2F0aXZlLiBUaGVuIE9sbGllLCB0aGUgc2Vjb25kIHBsYXllciwgZG9lcyB0aGUgc2FtZSB3aXRoIHRoZSB0d28gcmVzdWx0aW5nIG51bWJlcnMsIHRoZW4gU3RhbiwgZXRjLiwgYWx0ZXJuYXRlbHksIHVudGlsIG9uZSBwbGF5ZXIgaXMgYWJsZSB0byBzdWJ0cmFjdCBhIG11bHRpcGxlIG9mIHRoZSBsZXNzZXIgbnVtYmVyIGZyb20gdGhlIGdyZWF0ZXIgdG8gcmVhY2ggMCwgYW5kIHRoZXJlYnkgd2lucy4gRm9yIGV4YW1wbGUsIHRoZSBwbGF5ZXJzIG1heSBzdGFydCB3aXRoICgyNSw3KTo8XC9wPlxyXG5cclxuPHByZT5cclxuMjUgNyBcclxuMTEgNyBcclxuIDQgNyBcclxuIDQgMyBcclxuIDEgMyBcclxuIDEgMDxcL3ByZT5cclxuXHJcbjxwPmFuIFN0YW4gd2lucy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIG51bWJlciBvZiBsaW5lcy4gRWFjaCBsaW5lIGNvbnRhaW5zIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyBnaXZpbmcgdGhlIHN0YXJ0aW5nIHR3byBudW1iZXJzIG9mIHRoZSBnYW1lLiBTdGFuIGFsd2F5cyBzdGFydHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggbGluZSBvZiBpbnB1dCwgb3V0cHV0IG9uZSBsaW5lIHNheWluZyBlaXRoZXIgU3RhbiB3aW5zIG9yIE9sbGllIHdpbnMgYXNzdW1pbmcgdGhhdCBib3RoIG9mIHRoZW0gcGxheSBwZXJmZWN0bHkuIFRoZSBsYXN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIHplcm9lcyBhbmQgc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d