The Sparsest Number in Between

시간 제한2초메모리 제한2048 MB

요약

1 이상 10^18 이하의 a, b가 주어질 때 [a, b] 구간에서 이진수로 표현했을 때 1의 개수가 가장 적으면서 그중 가장 작은 수를 찾는다.

난이도: 보통10점 중 7점
유형: 비트 연산, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

You are given a pair of positive integers $a$ and $b$ ( $a ≤ b$ ). Among those integers between $a$ and $b$ , inclusive, your task is to find the sparsest one, that is, the one with the least number of 1’s in its binary representation. If there are two or more such integers, you should find the smallest among them.

Suppose, for instance, that $a = 10$ and $b = 13$ . The integers between $a$ and $b$ , inclusive, are $10$ , $11$ , $12$ , and $13$ , and their binary representations are 1010, 1011, 1100, and 1101, respectively. Thus, in this case, the answer is $10$ , since $10$ and $12$ have the least number of 1’s in their binary representations and $10$ is smaller than $12$ .

입력

The input consists of a single test case of the following format.

$a$ $b$

Here, $a$ and $b$ ( $a ≤ b$ ) are integers between $1$ and $10^{18}$ , inclusive.

출력

Output a line containing the smallest among the sparsest integers between $a$ and $b$ , inclusive.

예제5

예제 1
입력
```
10 13
```
예상 출력
```
10
```
예제 2
입력
```
11 15
```
예상 출력
```
12
```
예제 3
입력
```
11 20
```
예상 출력
```
16
```
예제 4
입력
```
1 1000000000000000000
```
예상 출력
```
1
```
예제 5
입력
```
9876543210 9876543210
```
예상 출력
```
9876543210
```