시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 103 42 34 48.571%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

2 3

예제 출력 1

21845 32767
W3sicHJvYmxlbV9pZCI6IjIxMzciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YmQ4NFx1YzIxOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjZWY0XHVkNGU4XHVkMTMwXHVhYzAwIFx1YWUzMFx1YmNmOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzQwIFx1Yzc3NFx1YzljNFx1YzIxOFx1YzVkMCBcdWFlMzBcdWJjMThcdWQ1NWMgXHVjODE1XHVjMjE4IFx1YmZkMFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzc3NFx1Yjk3YyBcdWM3NzRcdWM2YTlcdWQ1NThcdWM1ZWMgXHVjMmU0XHVjMjE4KFx1YzE4Y1x1YzIxOClcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWYwXHVhZDZjXHViNDE4XHVjNWI0IFx1YzY1NFx1YjJlNC4gXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMCBcdWJjMjlcdWJjOTVcdWI0ZTQgXHVjOTExXHVjNWQwXHVjMTFjIFx1ZDYwNFx1YzdhY1x1YjI5NCBcdWJkODBcdWIzZDkgXHVjMThjXHVjMjE4XHVjODEwIFx1YmMyOVx1YzJkZFx1Yzc3NCBcdWNjNDRcdWQwZGRcdWI0MThcdWM1YjQgXHViMTEwXHViOWFjIFx1YzBhY1x1YzZhOVx1YjQxOFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYyBcdWM3NzQgXHViYzI5XHViYzk1XHVjNzQwIFx1YzYyNFx1Y2MyOCBcdWI0ZjFcdWM3NTggXHViYjM4XHVjODFjXHVhYzAwIFx1Yzc4OFx1YjI5NCBcdWM2NDRcdWJjYmRcdWQ1NThcdWM5YzAgXHViYWJiXHVkNTVjIFx1YmMyOVx1YmM5NVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmY5XHVjMmUwXHVjNzQwIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWIyZTRcdWI4ZThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1ZDU1OFx1YjA5OCBcdWMxMjRcdWFjYzRcdWQ1NThcdWFjOGMgXHViNDE4XHVjNWM4XHViMjk0XHViMzcwLCBcdWM3NzQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4IFx1YzU0OFx1YzVkMFx1YzExYyBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI5N2MgXHVjNzc0XHVjNmE5XHVkNTU4XHVjNWVjIFx1YzJlNFx1YzIxOFx1Yjk3YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjMTI0XHVhY2M0XHVkNTU4XHViMjk0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWMyZTRcdWMyMThcdWI0ZTRcdWM3NTggXHViMzAwXHVjMThjIFx1YmU0NFx1YWQ1MFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVjMGI0XHVkM2I0XHViY2Y0XHVhYzhjIFx1YjQxOFx1YzVjOFx1YWNlMCwgXHVjNzc0IFx1YWNmY1x1YzgxNVx1YzVkMFx1YzExYyBcdWQ1NWMgXHVjMmU0XHVjMjE4XHVjNWQwIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNGNcdWM2YjQgXHViZDg0XHVjMjE4XHVhYzAwIFx1YmIzNFx1YzVjN1x1Yzc3OFx1YzljMCBcdWM1NGNcdWM1NDRcdWJjZjRcdWFjZTAgXHVjMmY2XHVjNWI0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFlMzBcdWM1N2RcdWJkODRcdWMyMTggXHVkNTU4XHViMDk4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Yzc3NCBcdWJkODRcdWMyMThcdWM1ZDAgXHVhYzAwXHVjN2E1IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFlMzBcdWM1N2RcdWJkODRcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YWMwMFx1YzdhNSBcdWFjMDBcdWFlNWRcdWIyZTRcdWIyOTQgXHViOWQwXHVjNzQwLCBcdWJiM2NcdWI4NjAgXHViNDUwIFx1YmQ4NFx1YzIxOFx1YWMwMCBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWIyOTQgXHVjMmU0XHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1YWMwMCBcdWNkNWNcdWMxOGNcdWM3NzRcdWJhNzAsIFx1Yzc5MFx1YWUzMCBcdWM3OTBcdWMyZTBcdWFjZmNcdWIyOTQgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVhZTMwXHVjNTdkXHViZDg0XHVjMjE4XHVhYzAwIFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzZiMFx1YjlhY1x1YWMwMCBcdWIyZTRcdWI4ZThcdWIyOTQgXHViZDg0XHVjMjE4XHViNGU0XHVjNzQwIFx1YmQ4NFx1YmFhOFx1YzY0MCBcdWJkODRcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIDEgXHVjNzc0XHVjMGMxIDMyNzY3IFx1Yzc3NFx1ZDU1OFx1Yjc3Y1x1YWNlMCBcdWFjMDBcdWM4MTVcdWQ1NThcdWM3OTAuIFx1YWUzMFx1YzU3ZFx1YmQ4NFx1YzIxOFx1Yjc4MCBcdWJkODRcdWJhYThcdWM2NDAgXHViZDg0XHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YjMwMCBcdWFjZjVcdWM1N2RcdWMyMThcdWFjMDAgMVx1Yzc3OCBcdWJkODRcdWMyMThcdWI5N2MgXHViOWQwXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJkODRcdWMyMThcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YmQ4NFx1Yzc5MFx1YzY0MCBcdWJkODRcdWJhYThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOyhcdWIyZTgsIFx1YmQ4NFx1Yzc5MFx1YjI5NCBcdWJkODRcdWJhYThcdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1Y2MzZVx1YjI5NCBcdWJkODRcdWMyMThcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YmQ4NFx1Yzc5MFx1YzY0MCBcdWJkODRcdWJhYThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU3NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjEzNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNsb3NlIEVuY291bnRlciIsImRlc2NyaXB0aW9uIjoiPHA+TGFja2luZyBldmVuIGEgZmlmdGggZ3JhZGUgZWR1Y2F0aW9uLCB0aGUgY293cyBhcmUgaGF2aW5nIHRyb3VibGUgd2l0aCBhIGZyYWN0aW9uIHByb2JsZW0gZnJvbSB0aGVpciB0ZXh0Ym9vay4gUGxlYXNlIGhlbHAgdGhlbS4gVGhlIHByb2JsZW0gaXMgc2ltcGxlOiZuYnNwOzxcL3A+XHJcblxyXG48cD5HaXZlbiBhIHByb3Blcmx5IHJlZHVjZWQgZnJhY3Rpb24gKGkuZS4sIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBpcyAxLCBzbyB0aGUgZnJhY3Rpb24gY2Fubm90IGJlIGZ1cnRoZXIgcmVkdWNlZCkgZmluZCB0aGUgc21hbGxlc3QgcHJvcGVybHkgcmVkdWNlZCBmcmFjdGlvbiB3aXRoIG51bWVyYXRvciBhbmQgZGVub21pbmF0b3IgaW4gdGhlIHJhbmdlIDEuLjMyLDc2NyB0aGF0IGlzIGNsb3Nlc3QgKGJ1dCBub3QgZXF1YWwpIHRvIHRoZSBnaXZlbiBmcmFjdGlvbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUd28gcG9zaXRpdmUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzIE4gYW5kIEQgKDEgJmxlOyBOICZsdDsgRCAmbGU7IDMyLDc2NyksIHJlc3BlY3RpdmVseSB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBvZiB0aGUgZ2l2ZW4gZnJhY3Rpb248XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IFR3byBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMsIHJlc3BlY3RpdmVseSB0aGUgbnVtZXJhdG9yIGFuZCBkZW5vbWluYXRvciBvZiB0aGUgc21hbGxlc3QsIGNsb3Nlc3QgZnJhY3Rpb24gZGlmZmVyZW50IGZyb20gdGhlIGlucHV0IGZyYWN0aW9uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=