노드가 \(2,100,000,000\)개인 완전 이진 트리가 있다. 루트 노드의 번호는 1이며, 노드의 번호는 위에서 아래로, 같은 깊이에서는 왼쪽에서 오른쪽으로 1부터 차례대로 부여된다.

1번부터 7번까지의 노드를 나타내면 다음과 같다.

어떤 노드의 조상은 그 노드 자신, 그 노드의 부모, 부모의 부모와 같이 루트까지 이어지는 노드들을 의미한다.

두 노드 \(a\)와 \(b\)의 공통 조상 가운데 두 노드에 가장 가까운 노드를 가장 가까운 공통 조상(Lowest Common Ancestor, LCA)이라고 한다.

예를 들어 3번 노드와 4번 노드의 가장 가까운 공통 조상은 1번 노드이고, 6번 노드와 7번 노드의 가장 가까운 공통 조상은 3번 노드이다.

두 노드 \(a\)와 \(b\)가 주어졌을 때, 두 노드의 가장 가까운 공통 조상 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 노드의 번호 \(a\)와 \(b\)가 공백을 사이에 두고 주어진다.

출력

두 노드의 가장 가까운 공통 조상 번호를 출력한다.

제한 사항

• \(1 \le a,b \le 2,100,000,000\)

다음 문자열은 소스 코드에 포함될 수 없다.

• for
• while
• goto

예제 입력 1

3 4

예제 출력 1

1

예제 설명 1

3번 노드의 조상은 3번과 1번 노드이고, 4번 노드의 조상은 4번, 2번, 1번 노드이다. 두 노드의 공통 조상은 1번 노드이다.

예제 입력 2

6 7

예제 출력 2

3

예제 설명 2

6번 노드와 7번 노드는 모두 3번 노드의 자식이므로 가장 가까운 공통 조상은 3번 노드이다.