D - XOR World

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

f(A, B)A, A+1, ..., B の排他的論理和としたとき、f(A, B) を求めてください。

排他的論理和とは

整数 c_1, c_2, ..., c_n のビットごとの排他的論理和 y は、以下のように定義されます。

  • y を二進表記した際の 2^k (k \geq 0) の位の数は、c_1, c_2, ..., c_n のうち、二進表記した際の 2^k の位の数が 1 となるものが奇数個ならば 1、偶数個ならば 0 である。

例えば、35 の排他的論理和は 6 です(二進数表記すると: 011101 の排他的論理和は 110 です)。

制約

  • 入力は全て整数である。
  • 0 \leq A \leq B \leq 10^{12}

入力

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

A B

出力

f(A, B) を計算し、出力せよ。


入力例 1

2 4

出力例 1

5

2, 3, 42 進数でそれぞれ 010, 011, 100 です。 これらの排他的論理和は 101 であり、これを 10 進数表記にすると 5 になります。


入力例 2

123 456

出力例 2

435

入力例 3

123456789012 123456789012

出力例 3

123456789012

Score : 400 points

Problem Statement

Let f(A, B) be the exclusive OR of A, A+1, ..., B. Find f(A, B).

What is exclusive OR?

The bitwise exclusive OR of integers c_1, c_2, ..., c_n (let us call it y) is defined as follows:

  • When y is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if, the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place, is odd, and 0 if that count is even.

For example, the exclusive OR of 3 and 5 is 6. (When written in base two: the exclusive OR of 011 and 101 is 110.)

Constraints

  • All values in input are integers.
  • 0 \leq A \leq B \leq 10^{12}

Input

Input is given from Standard Input in the following format:

A B

Output

Compute f(A, B) and print it.


Sample Input 1

2 4

Sample Output 1

5

2, 3, 4 are 010, 011, 100 in base two, respectively. The exclusive OR of these is 101, which is 5 in base ten.


Sample Input 2

123 456

Sample Output 2

435

Sample Input 3

123456789012 123456789012

Sample Output 3

123456789012