A. Blackout Math
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Turjo and Urjo are two exceptionally good brothers. One lazy Friday afternoon, the power went out, leaving them completely bored with nothing to do. To pass the time, Urjo decided to invent a math game to challenge Turjo's calculating speed.

Urjo grabs a piece of paper and writes down two starting numbers, $$$A$$$ and $$$B$$$. He then tells Turjo that he is generating a special sequence. However, since standard addition is way too easy for them, Urjo uses the Bitwise XOR operator ($$$\oplus$$$) to generate the next terms.

Let $$$F$$$ be a sequence. The sequence is defined by Urjo as follows:

$$$$$$F_{1} = A$$$$$$ $$$$$$F_{2} = B$$$$$$ $$$$$$F_{i} = F_{i-1} \oplus F_{i-2} \ for \ all \ i \ge 3$$$$$$

The rules of the game are simple: Urjo will suddenly shout a number $$$N$$$. In order to win the game and prove he is the superior brother, Turjo must instantly shout back the exact value of the $$$N^{th}$$$ term in the sequence defined as $$$F_{N}$$$.

He needs your help to write a lightning-fast program so he can beat his brother and win the game!

Constraints

  • $$$1 \le N \le 10^{18}$$$
  • $$$0 \le A, B \le 10^{18}$$$
Input

Input is given in the following format:

  • line 1: $$$N \quad A \quad B$$$
Output
  • line 1: A single integer denoting the exact value of the $$$F_{N}$$$.
Scoring
SubtaskPointsAdd. constraints
$$$1$$$$$$5$$$$$$N \le 3$$$
$$$2$$$$$$7$$$$$$A = 1$$$ and $$$B = 1$$$ and $$$N \le 10$$$
$$$3$$$$$$8$$$$$$N \le 20$$$
$$$4$$$$$$10$$$$$$N \le 1000$$$
$$$5$$$$$$30$$$$$$N \le 10^5$$$
$$$6$$$$$$40$$$No additional constraints
Examples
Input
3 6 7
Output
1
Input
5 9 11
Output
11
Note

Example 1: $$$N=3 \quad A=6 \quad B=7$$$

  • $$$F_{1} = 6$$$
  • $$$F_{2} = 7$$$
  • $$$F_{3} = F_{2} \oplus F_{1} = 7 \oplus 6 = 1$$$

Example 2: $$$N=5 \quad A=9 \quad B=11$$$

  • $$$F_{1} = 9$$$
  • $$$F_{2} = 11$$$
  • $$$F_{3} = F_{2} \oplus F_{1} = 11 \oplus 9 = 2$$$
  • $$$F_{4} = F_{3} \oplus F_{2} = 2 \oplus 11 = 9$$$
  • $$$F_{5} = F_{4} \oplus F_{3} = 9 \oplus 2 = 11$$$

Bitwise XOR ($$$\oplus$$$) compares two numbers in their binary representation. It evaluates each pair of bits according to the following truth table:

ABA $$$\oplus$$$ B
000
011
101
110
For example, $$$6 \oplus 7 = 1$$$
  • 6 in binary is 00110
  • 7 in binary is 00111
Comparing them bit-by-bit yields 00001, which is 1 in decimal.