시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 590 252 198 40.909%

문제

다음과 같은 귀납적인 규칙에 의해서 만들어지는 무한한 크기의 이진 트리를 생각하자. 각각의 노드에는 두 정수의 순서쌍이 할당되어 있다.

  1. 루트에는 (1, 1)이 할당된다.
  2. 어떤 노드가 (a, b)가 할당되었을 때, 그 노드의 왼쪽 자식에는 (a+b, b)가 할당되고, 오른쪽 자식에는 (a, a+b)가 할당된다.

우리는 어떤 노드가 주어졌을 때, 루트에서 그 노드로 이동하는 최단 경로를 찾으려 한다. 하지만 최단 경로가 매우 길 수도 있기 때문에, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 찾으려고 한다.

입력으로 두 정수 A, B가 주어졌을 때, 루트에서 (A, B)가 할당된 노드까지 최단 경로로 이동할 때, 왼쪽 자식으로 이동하는 회수와 오른쪽 자식으로 이동하는 회수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 A, B(1≤A, B≤2,000,000,000)가 주어진다. 잘못된 입력은 주어지지 않는다고 가정한다.

출력

첫째 줄에 두 정수 L, R을 출력한다. 각각은 왼쪽으로 이동한 회수, 오른쪽으로 이동한 회수를 나타낸다.

예제 입력 1

3 4

예제 출력 1

2 1
W3sicHJvYmxlbV9pZCI6IjIwNzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiMzRcdWQ1NWNcdWM3NzRcdWM5YzRcdWQyYjhcdWI5YWMiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVhZGMwXHViMGE5XHVjODAxXHVjNzc4IFx1YWRkY1x1Y2U1OVx1YzVkMCBcdWM3NThcdWQ1NzRcdWMxMWMgXHViOWNjXHViNGU0XHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzNFx1ZDU1Y1x1ZDU1YyBcdWQwNmNcdWFlMzBcdWM3NTggXHVjNzc0XHVjOWM0IFx1ZDJiOFx1YjlhY1x1Yjk3YyBcdWMwZGRcdWFjMDFcdWQ1NThcdWM3OTAuIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxNzhcdWI0ZGNcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWMyMWNcdWMxMWNcdWMzMGRcdWM3NzQgXHVkNTYwXHViMmY5XHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWI4ZThcdWQyYjhcdWM1ZDBcdWIyOTQgKDEsIDEpXHVjNzc0IFx1ZDU2MFx1YjJmOVx1YjQxY1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjNWI0XHViNWE0IFx1YjE3OFx1YjRkY1x1YWMwMCAoYSwgYilcdWFjMDAgXHVkNTYwXHViMmY5XHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVhZGY4IFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWM2N2NcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNWQwXHViMjk0IChhK2IsIGIpXHVhYzAwIFx1ZDU2MFx1YjJmOVx1YjQxOFx1YWNlMCwgXHVjNjI0XHViOTc4XHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzVkMFx1YjI5NCAoYSwgYStiKVx1YWMwMCBcdWQ1NjBcdWIyZjlcdWI0MWNcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG5cclxuPHA+XHVjNmIwXHViOWFjXHViMjk0IFx1YzViNFx1YjVhNCBcdWIxNzhcdWI0ZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOGU4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YWRmOCBcdWIxNzhcdWI0ZGNcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjYzNlXHVjNzNjXHViODI0IFx1ZDU1Y1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjIFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWFjMDAgXHViOWU0XHVjNmIwIFx1YWUzOCBcdWMyMThcdWIzYzQgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjNjdjXHVjYWJkIFx1Yzc5MFx1YzJkZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHVkNjhjXHVjMjE4XHVjNjQwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWNjM2VcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3M2NcdWI4NWMgXHViNDUwIFx1YzgxNVx1YzIxOCBBLCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YjhlOFx1ZDJiOFx1YzVkMFx1YzExYyAoQSwgQilcdWFjMDAgXHVkNTYwXHViMmY5XHViNDFjIFx1YjE3OFx1YjRkY1x1YWU0Y1x1YzljMCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGMsIFx1YzY3Y1x1Y2FiZCBcdWM3OTBcdWMyZGRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1ZDY4Y1x1YzIxOFx1YzY0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHVjNzkwXHVjMmRkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWQ2OGNcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViMGI0XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjQ1MCBcdWM4MTVcdWMyMTggQSwgQigxJmxlO0EsIEImbGU7MiwwMDAsMDAwLDAwMClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3OThcdWJhYmJcdWI0MWMgXHVjNzg1XHViODI1XHVjNzQwIFx1YzhmY1x1YzViNFx1YzljMFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNDUwIFx1YzgxNVx1YzIxOCBMLCBSXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzQwIFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NWMgXHVkNjhjXHVjMjE4LCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTVjIFx1ZDY4Y1x1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjA3OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkJpbmFyeSBUcmVlIiwiZGVzY3JpcHRpb24iOiI8cD5CaW5hcnkgdHJlZXMgYXJlIGEgY29tbW9uIGRhdGEgc3RydWN0dXJlIGluIGNvbXB1dGVyIHNjaWVuY2UuIEluIHRoaXMgcHJvYmxlbSB3ZSB3aWxsIGxvb2sgYXQgYW4gaW5maW5pdGUgYmluYXJ5IHRyZWUgd2hlcmUgdGhlIG5vZGVzIGNvbnRhaW4gYSBwYWlyIG9mIGludGVnZXJzLiBUaGUgdHJlZSBpcyBjb25zdHJ1Y3RlZCBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlIHJvb3QgY29udGFpbnMgdGhlIHBhaXIgKDEsIDEpLjxcL2xpPlxyXG5cdDxsaT5JZiBhIG5vZGUgY29udGFpbnMgKGEsIGIpIHRoZW4gaXRzIGxlZnQgY2hpbGQgY29udGFpbnMgKGEgKyBiLCBiKSBhbmQgaXRzIHJpZ2h0IGNoaWxkIChhLCBhICsgYik8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5HaXZlbiB0aGUgY29udGVudHMgKGEsIGIpIG9mIHNvbWUgbm9kZSBvZiB0aGUgYmluYXJ5IHRyZWUgZGVzY3JpYmVkIGFib3ZlLCBzdXBwb3NlIHlvdSBhcmUgd2Fsa2luZyBmcm9tIHRoZSByb290IG9mIHRoZSB0cmVlIHRvIHRoZSBnaXZlbiBub2RlIGFsb25nIHRoZSBzaG9ydGVzdCBwb3NzaWJsZSBwYXRoLiBDYW4geW91IGZpbmQgb3V0IGhvdyBvZnRlbiB5b3UgaGF2ZSB0byBnbyB0byBhIGxlZnQgY2hpbGQgYW5kIGhvdyBvZnRlbiB0byBhIHJpZ2h0IGNoaWxkPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiBzY2VuYXJpb3MuPFwvcD5cclxuXHJcbjxwPkV2ZXJ5IHNjZW5hcmlvIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0d28gaW50ZWdlcnMgaSBhbmQgaiAoMSAmbGU7IGksIGogJmxlOyAyJm1pZGRvdDsxMDxzdXA+OTxcL3N1cD4pIHRoYXQgcmVwcmVzZW50IGEgbm9kZSAoaSwgaikuIFlvdSBjYW4gYXNzdW1lIHRoYXQgdGhpcyBpcyBhIHZhbGlkIG5vZGUgaW4gdGhlIGJpbmFyeSB0cmVlIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IGZvciBldmVyeSBzY2VuYXJpbyBiZWdpbnMgd2l0aCBhIGxpbmUgY29udGFpbmluZyAmbGRxdW87U2NlbmFyaW8gI2k6JnJkcXVvOywgd2hlcmUgaSBpcyB0aGUgbnVtYmVyIG9mIHRoZSBzY2VuYXJpbyBzdGFydGluZyBhdCAxLiBUaGVuIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0d28gbnVtYmVycyBsIGFuZCByIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZSwgd2hlcmUgbCBpcyBob3cgb2Z0ZW4geW91IGhhdmUgdG8gZ28gbGVmdCBhbmQgciBpcyBob3cgb2Z0ZW4geW91IGhhdmUgdG8gZ28gcmlnaHQgd2hlbiB0cmF2ZXJzaW5nIHRoZSB0cmVlIGZyb20gdGhlIHJvb3QgdG8gdGhlIG5vZGUgZ2l2ZW4gaW4gdGhlIGlucHV0LiBQcmludCBhbiBlbXB0eSBsaW5lIGFmdGVyIGV2ZXJ5IHNjZW5hcmlvLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==