A - Smaller XOR Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300

問題文

整数 N,L,R が与えられます. 以下の条件を両方満たす整数 x の個数を数えてください.

  • L \leq x \leq R
  • (x \oplus N) < N (ここで \oplus はビット単位 \mathrm{XOR} 演算を表す)
ビット単位 \mathrm{XOR} 演算とは

整数 A, B のビット単位 \mathrm{XOR}A \oplus B は、以下のように定義されます。

  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101 = 110)。

制約

  • 1 \leq N \leq 10^{18}
  • 1 \leq L \leq R \leq 10^{18}
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる.

N L R

出力

答えを出力せよ.


入力例 1

2 1 2

出力例 1

1

x=1 の場合,L \leq x \leq R は満たしますが,(x \oplus N) < N は満たしません. x=2 の場合,両方の条件を満たします. 他に条件を満たす x は存在しません.


入力例 2

10 2 19

出力例 2

10

入力例 3

1000000000000000000 1 1000000000000000000

出力例 3

847078495393153025

Score : 300 points

Problem Statement

Given are integers N, L, and R. Count the number of integers x that satisfy both of the following conditions.

  • L \leq x \leq R
  • (x \oplus N) < N (Here, \oplus denotes the bitwise \mathrm{XOR}.)
What is the bitwise \mathrm{XOR}?

The bitwise \mathrm{XOR} of integers A and B, A\oplus B, is defined as follows:

  • When A\oplus B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if exactly one of A and B is 1, and 0 otherwise.
For example, we have 3\oplus 5 = 6 (in base two: 011\oplus 101 = 110).

Constraints

  • 1 \leq N \leq 10^{18}
  • 1 \leq L \leq R \leq 10^{18}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N L R

Output

Print the answer.


Sample Input 1

2 1 2

Sample Output 1

1

For x=1, L \leq x \leq R is satisfied, but (x \oplus N) < N is not. For x=2, both conditions are satisfied. There is no other x that satisfies the conditions.


Sample Input 2

10 2 19

Sample Output 2

10

Sample Input 3

1000000000000000000 1 1000000000000000000

Sample Output 3

847078495393153025