시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 378 66 51 22.768%

문제

유클리드 게임은 두 명이서 하는 게임이고, 자연수 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+XHJcblxyXG48cD5cclxuXHRcdWIzZDlcdWQ2MDFcdWM3NzRcdWM2NDAgXHViM2Q5XHVhZGRjXHViMjk0IFx1YzcyMFx1ZDA3NFx1YjlhY1x1YjRkYyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWMyZGNcdWM3OTFcdWQ1NWNcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWQwNzAgXHVjMjE4XHViOTdjIFx1Yzc5MVx1Yzc0MCBcdWMyMThcdWM3NTggXHViYzMwXHVjMjE4XHViOWNjXHVkMDdjIFx1YmU4MFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWQwNzAgXHVjMjE4XHViMjk0IFx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4XHVhYzAwIFx1YjQxOFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuJm5ic3A7PFwvcD5cclxuPHA+XHJcblx0XHVhZGY4XHViN2YwIFx1YjJlNFx1Yzc0YyBcdWIzZDlcdWFkZGNcdWIyOTQgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWFjODNcdWFjZmMgXHViNjExXHVhYzE5XHVjNzc0IFx1ZDA3MCBcdWMyMThcdWI5N2MgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yzc1OCBcdWJjMzBcdWMyMThcdWI5Y2NcdWQwN2MgXHViZTgwXHViMmU0LiBcdWM3NzRcdWI3ZjBcdWMyZGRcdWM3M2NcdWI4NWMgXHViNDUwIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCBcdWMxMWNcdWI4NWMgXHViYzg4XHVhYzA4XHVjNTQ0XHVhYzAwXHViYTc0XHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVkMDcwIFx1YzIxOFx1Yjk3YyAwXHVjNzNjXHViODVjIFx1YjljY1x1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJiOVx1YjlhY1x1ZDU1OFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgKDI1LCA3KVx1Yjg1YyBcdWMyZGNcdWM3OTFcdWQ1NWMgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzBkZFx1YWMwMVx1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHJcblx0MjUgNzxcL3A+XHJcbjxwPlxyXG5cdDExIDc8XC9wPlxyXG48cD5cclxuXHQ0IDc8XC9wPlxyXG48cD5cclxuXHQ0IDM8XC9wPlxyXG48cD5cclxuXHQxIDM8XC9wPlxyXG48cD5cclxuXHQxIDA8XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzA0XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhYzhjIFx1YjQxOFx1YmE3NCwgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwXHVjNzc0XHVhZTMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gKFx1ZDA3MCBcdWMyMThcdWM2NDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1YjI5NCBcdWFjMDEgXHVkMTM0XHVjNWQwXHVjMTFjIFx1ZDA3MCBcdWMyMThcdWM2NDAgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yzc3NFx1YjJlNC4pPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjQ1MCBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWFjMDAgXHVjZDVjXHVjODAxXHVjNzU4IFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTYwIFx1YjU0YywgXHViMjA0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVhYzhjXHVjNzg0XHVjNzQ0IFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjMjJiXHVjNzkwXHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1YmEzY1x1YzgwMCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4XHViMjk0IDI8c3VwPjMxPFwvc3VwPi0xXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDAgXHViNDUwIFx1YWMxY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVhYzAxIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgXHViM2Q5XHVkNjAxXHVjNzc0XHVhYzAwIFx1Yzc3NFx1YWUzMFx1YmE3NCBBIHdpbnNcdWI5N2MsIFx1YjNkOVx1YWRkY1x1YWMwMCBcdWM3NzRcdWFlMzBcdWJhNzQgQiB3aW5zXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzQyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRXVjbGlkJ3MgR2FtZSIsImRlc2NyaXB0aW9uIjoiPHA+VHdvIHBsYXllcnMsIFN0YW4gYW5kIE9sbGllLCBwbGF5LCBzdGFydGluZyB3aXRoIHR3byBuYXR1cmFsIG51bWJlcnMuIFN0YW4sIHRoZSBmaXJzdCBwbGF5ZXIsIHN1YnRyYWN0cyBhbnkgcG9zaXRpdmUgbXVsdGlwbGUgb2YgdGhlIGxlc3NlciBvZiB0aGUgdHdvIG51bWJlcnMgZnJvbSB0aGUgZ3JlYXRlciBvZiB0aGUgdHdvIG51bWJlcnMsIHByb3ZpZGVkIHRoYXQgdGhlIHJlc3VsdGluZyBudW1iZXIgbXVzdCBiZSBub25uZWdhdGl2ZS4gVGhlbiBPbGxpZSwgdGhlIHNlY29uZCBwbGF5ZXIsIGRvZXMgdGhlIHNhbWUgd2l0aCB0aGUgdHdvIHJlc3VsdGluZyBudW1iZXJzLCB0aGVuIFN0YW4sIGV0Yy4sIGFsdGVybmF0ZWx5LCB1bnRpbCBvbmUgcGxheWVyIGlzIGFibGUgdG8gc3VidHJhY3QgYSBtdWx0aXBsZSBvZiB0aGUgbGVzc2VyIG51bWJlciBmcm9tIHRoZSBncmVhdGVyIHRvIHJlYWNoIDAsIGFuZCB0aGVyZWJ5IHdpbnMuIEZvciBleGFtcGxlLCB0aGUgcGxheWVycyBtYXkgc3RhcnQgd2l0aCAoMjUsNyk6PFwvcD5cclxuXHJcbjxwcmU+XHJcbjI1IDcgXHJcbjExIDcgXHJcbiA0IDcgXHJcbiA0IDMgXHJcbiAxIDMgXHJcbiAxIDA8XC9wcmU+XHJcblxyXG48cD5hbiBTdGFuIHdpbnMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2YgbGluZXMuIEVhY2ggbGluZSBjb250YWlucyB0d28gcG9zaXRpdmUgaW50ZWdlcnMgZ2l2aW5nIHRoZSBzdGFydGluZyB0d28gbnVtYmVycyBvZiB0aGUgZ2FtZS4gU3RhbiBhbHdheXMgc3RhcnRzLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGxpbmUgb2YgaW5wdXQsIG91dHB1dCBvbmUgbGluZSBzYXlpbmcgZWl0aGVyIFN0YW4gd2lucyBvciBPbGxpZSB3aW5zIGFzc3VtaW5nIHRoYXQgYm90aCBvZiB0aGVtIHBsYXkgcGVyZmVjdGx5LiBUaGUgbGFzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byB6ZXJvZXMgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==