시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 107 45 37 50.000%

문제

컴퓨터가 기본적으로 지원하는 것은 이진수에 기반한 정수 뿐이기 때문에, 이를 이용하여 실수(소수)를 표현하기 위한 방법이 연구되어 왔다. 여러 가지 방법들 중에서 현재는 부동 소수점 방식이 채택되어 널리 사용되고 있다. 하지만 이 방법은 오차 등의 문제가 있는 완벽하지 못한 방법이다.

당신은 실수를 다루는 프로그램을 하나 설계하게 되었는데, 이 프로그램 안에서 기약분수를 이용하여 실수를 표현하기로 하였다. 프로그램을 설계하는 과정에서 실수들의 대소 비교에 대해 살펴보게 되었고, 이 과정에서 한 실수에 가장 가까운 분수가 무엇인지 알아보고 싶어졌다.

기약분수 하나가 주어졌을 때, 이 분수에 가장 가까운 기약분수를 구하는 프로그램을 작성하시오. 가장 가깝다는 말은, 물론 두 분수가 표현하는 실수의 차이가 최소이며, 자기 자신과는 달라야 한다. 또, 그러한 기약분수가 여러 가지인 경우 가장 작은 것이다.

우리가 다루는 분수들은 분모와 분자가 모두 1 이상 32767 이하라고 가정하자. 기약분수란 분모와 분자의 최대 공약수가 1인 분수를 말한다.

입력

첫째 줄에 분수를 표현하는 분자와 분모가 주어진다. (단, 분자는 분모보다 작다)

출력

첫째 줄에 우리가 찾는 분수를 표현하는 분자와 분모를 공백으로 구분해 출력한다.

예제 입력 1

2 3

예제 출력 1

21845 32767
W3sicHJvYmxlbV9pZCI6IjIxMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YmQ4NFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZWY0XHVkNGU4XHVkMTMwXHVhYzAwIFx1YWUzMFx1YmNmOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Yzc3NFx1YzljNFx1YzIxOFx1YzVkMCBcdWFlMzBcdWJjMThcdWQ1NWMgXHVjODE1XHVjMjE4IFx1YmZkMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3NFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjMmU0XHVjMjE4KFx1YzE4Y1x1YzIxOClcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWYwXHVhZDZjXHViNDE4XHVjNWI0IFx1YzY1NFx1YjJlNC4gXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDYwNFx1YzdhY1x1YjI5NCBcdWJkODBcdWIzZDkgXHVjMThjXHVjMjE4XHVjODEwIFx1YmMyOVx1YzJkZFx1Yzc3NCBcdWNjNDRcdWQwZGRcdWI0MThcdWM1YjQgXHViMTEwXHViOWFjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzYyNFx1Y2MyOCBcdWI0ZjFcdWM3NTggXHViYjM4XHVjODFjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM2NDRcdWJjYmRcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWIyZTRcdWI4ZThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWMxMjRcdWFjYzRcdWQ1NThcdWFjOGMgXHViNDE4XHVjNWM4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzU0OFx1YzVkMFx1YzExYyBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NTggXHViMzAwXHVjMThjIFx1YmU0NFx1YWQ1MFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMGI0XHVkM2I0XHViY2Y0XHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCwgXHVjNzc0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWQ1NWMgXHVjMmU0XHVjMjE4XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViZDg0XHVjMjE4XHVhYzAwIFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWM1N2RcdWJkODRcdWMyMTggXHVkNTU4XHViMDk4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWJkODRcdWMyMThcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNWRcdWIyZTRcdWIyOTQgXHViOWQwXHVjNzQwLCBcdWJiM2NcdWI4NjAgXHViNDUwIFx1YmQ4NFx1YzIxOFx1YWMwMCBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWIyOTQgXHVjMmU0XHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBcdWNkNWNcdWMxOGNcdWM3NzRcdWJhNzAsIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWFjZmNcdWIyOTQgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVhYzAwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjBcdWI5YWNcdWFjMDAgXHViMmU0XHViOGU4XHViMjk0IFx1YmQ4NFx1YzIxOFx1YjRlNFx1Yzc0MCBcdWJkODRcdWJhYThcdWM2NDAgXHViZDg0XHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCAxIFx1Yzc3NFx1YzBjMSAzMjc2NyBcdWM3NzRcdWQ1NThcdWI3N2NcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHVjNzkwLiBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI3ODAgXHViZDg0XHViYWE4XHVjNjQwIFx1YmQ4NFx1Yzc5MFx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhY2Y1XHVjNTdkXHVjMjE4XHVhYzAwIDFcdWM3NzggXHViZDg0XHVjMjE4XHViOTdjIFx1YjlkMFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViZDg0XHVjMjE4XHViOTdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWJkODRcdWM3OTBcdWM2NDAgXHViZDg0XHViYWE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoXHViMmU4LCBcdWJkODRcdWM3OTBcdWIyOTQgXHViZDg0XHViYWE4XHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzZiMFx1YjlhY1x1YWMwMCBcdWNjM2VcdWIyOTQgXHViZDg0XHVjMjE4XHViOTdjIFx1ZDQ1Y1x1ZDYwNFx1ZDU1OFx1YjI5NCBcdWJkODRcdWM3OTBcdWM2NDAgXHViZDg0XHViYWE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjIxMzciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDbG9zZSBFbmNvdW50ZXIiLCJkZXNjcmlwdGlvbiI6IjxwPkxhY2tpbmcgZXZlbiBhIGZpZnRoIGdyYWRlIGVkdWNhdGlvbiwgdGhlIGNvd3MgYXJlIGhhdmluZyB0cm91YmxlIHdpdGggYSBmcmFjdGlvbiBwcm9ibGVtIGZyb20gdGhlaXIgdGV4dGJvb2suIFBsZWFzZSBoZWxwIHRoZW0uIFRoZSBwcm9ibGVtIGlzIHNpbXBsZTombmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBwcm9wZXJseSByZWR1Y2VkIGZyYWN0aW9uIChpLmUuLCB0aGUgZ3JlYXRlc3QgY29tbW9uIGRpdmlzb3Igb2YgdGhlIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3IgaXMgMSwgc28gdGhlIGZyYWN0aW9uIGNhbm5vdCBiZSBmdXJ0aGVyIHJlZHVjZWQpIGZpbmQgdGhlIHNtYWxsZXN0IHByb3Blcmx5IHJlZHVjZWQgZnJhY3Rpb24gd2l0aCBudW1lcmF0b3IgYW5kIGRlbm9taW5hdG9yIGluIHRoZSByYW5nZSAxLi4zMiw3NjcgdGhhdCBpcyBjbG9zZXN0IChidXQgbm90IGVxdWFsKSB0byB0aGUgZ2l2ZW4gZnJhY3Rpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVHdvIHBvc2l0aXZlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBOIGFuZCBEICgxICZsZTsgTiAmbHQ7IEQgJmxlOyAzMiw3NjcpLCByZXNwZWN0aXZlbHkgdGhlIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3Igb2YgdGhlIGdpdmVuIGZyYWN0aW9uPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUd28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzLCByZXNwZWN0aXZlbHkgdGhlIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3Igb2YgdGhlIHNtYWxsZXN0LCBjbG9zZXN0IGZyYWN0aW9uIGRpZmZlcmVudCBmcm9tIHRoZSBpbnB1dCBmcmFjdGlvbi48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d