시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 407 165 136 41.212%

문제

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

  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을 출력한다. 각각은 왼쪽으로 이동한 회수, 오른쪽으로 이동한 회수를 나타낸다.

예제 입력

3 4

예제 출력

2 1

힌트