시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 21 1 1 20.000%

## 문제

The operation “bitwise exclusive or” (we denote it with $\oplus$) is standardly defined on each couple of non-negative integers ($a$, $b$) as follows:

Let $a = \overline { a_{n-1}a_{n-2}a_{n-3}\cdots a_0}$ and $b = \overline { b_{n-1}b_{n-2}b_{n-3}\cdots b_0}$ be the $n$-digit binary notations of the number $a$ and $b$, i.e., $a_i$ and $b_i$ are zeroes or ones (if the binary digits of the smaller one are less than n, its notation is filled up with “leading zeroes”). Then the number $c = a \oplus b$ is defined in this way: its ith binary digit $c_i$ ($c = \overline {c_{n-1}c_{n-2}c_{n-3}\cdots c_0}$) is obtained by applying the operation “exclusive or” on the ith binary digits of $a$ and $b$ respectively, i. e., $c_i = a_i \text{ xor } b_i$ for each $i$ from $0$ to $n-1$. The xor operation is defined on binary digits as follows: $0 \text{ xor } 0 = 0$; $0 \text{ xor } 1 = 1$; $1 \text{ xor } 0 = 1$; $1 \text{ xor } 1 = 0$.

The operation is easily extended for more operands. More specifically, for the consecutive positive integers in the interval [$a$,$b$] we can denote $\oplus_{i=a}^{b} i = a \oplus (a+1) \oplus (a+2) \oplus \dots \oplus b$, assuming operation execution from left to right. Consider the positive integers $a$ and $b$ ($a$ < $b$), defining the closed interval of integers [$a$,$b$], as well as the positive integer $n$ ($1$ ≤ $n$ ≤ $b-a+1$). Consider the operation “bitwise exclusive or” on every possible $n$-tuple of consecutive integers in the interval [$a$,$b$].

Write a program xor to find out the largest value M which this process can produce.

Let’s, for clarity, take a closer look at the case $a=10$, $b=20$, $n=6$. I. e., we consider the interval [$10$, $20$] of integers, more precisely – all sextuples of consecutive integers in it. For each of them we apply the generalized operation “bitwise exclusive or”:

• $10 \oplus 11 \oplus 12 \oplus 13 \oplus 14 \oplus 15 = 1010_2 \oplus 1011_2 \oplus 1100_2 \oplus 1101_2 \oplus 1110_2 \oplus 1111_2 = 0001_2 = 1$
• $11 \oplus 12 \oplus 13 \oplus 14 \oplus 15 \oplus 16 = 1011_2 \oplus 1100_2 \oplus 1101_2 \oplus 1110_2 \oplus 1111_2 \oplus 10000_2 = 11011_2 = 27$
• $12 \oplus 13 \oplus 14 \oplus 15 \oplus 16 \oplus 17 = 1100_2 \oplus 1101_2 \oplus 1110_2 \oplus 1111_2 \oplus 10000_2 \oplus 10001_2 = 00001_2 = 1$
• $13 \oplus 14 \oplus 15 \oplus 16 \oplus 17 \oplus 18 = 1101_2 \oplus 1110_2 \oplus 1111_2 \oplus 10000_2 \oplus 10001_2 \oplus 10010_2 = 11111_2 = 31$
• $14 \oplus 15 \oplus 16 \oplus 17 \oplus 18 \oplus 19 = 1110_2 \oplus 1111_2 \oplus 10000_2 \oplus 10001_2 \oplus 10010_2 \oplus 10011_2 = 00001_2 = 1$
• $15 \oplus 16 \oplus 17 \oplus 18 \oplus 19 \oplus 20 = 1111_2 \oplus 10000_2 \oplus 10001_2 \oplus 10010_2 \oplus 10011_2 \oplus 10100_2 = 11011_2 = 27$

Obviously, in this case the solution is 31, resulting in the sextuple which starts with 13.

## 입력

One line is read from the standard input, containing the space separated positive integers $a$, $b$ and $n$.

$a$, $b$ and $n$ are positive integers with no more than 18 decimal digits; $a$ < $b$; $1$ < $n$ ≤ $b – a + 1$, $n$ < $10^8$.

## 출력

The program should write to the standard output one line, containing only one non-negative integer $M$ which is the biggest possible number, obtained by applying the operation “bitwise exclusive or” on at least one of the n-tuples of consecutive integers in the interval [$a$, $b$].

10 20 6

31