Problem B
XORsistinn 2
Languages
en
is
Gunnar the priest received a mysterious message by post yesterday that said that one of his parishioners might be possessed. On the back it said ,,You are our only hope XORsist!". Gunnar was in fact a sorcerer and had great experience in repelling spirits and demons.
He decided to write down the names of everyone at his sermon and ended up with names numbered from $1$ to $N$. Later he realized that he took the XOR of all the numbers from $a$ to $b$ that would give him information on who’s possessed; if the number is $0$ no one is possessed and if it’s between $1$ and $N$ then it would be the person on the list corresponding to that number. If it’s larger than $N$ it must be Gunnar himself that’s possessed and then we’re all in trouble!
Explanation of XOR
XOR, usually denoted by $~ \hat{}~ $ in programming languages, is an operation that takes two numbers and returns a new number. The operation is performed on the two numbers in binary , bit by bit. The following table shows how a new bit is calculated from the corresponding bits in the input numbers.
|
A |
B |
A XOR B |
|
1 |
1 |
0 |
|
1 |
0 |
1 |
|
0 |
1 |
1 |
|
0 |
0 |
0 |
Let us take an example. The number $1337$ in binary is 10100111001 and the number $1993$ in binary is 11111001001.
|
1337 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
1993 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1337 XOR 1993 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
The result is 01011110000 which is the number $752$.
Input
The first line contains an integer $N$, the number of parishioners at Gunnar’s sermon. The next line contains two integers, $a$ and $b$, $1 \leq a \leq b \leq N$.
Output
Print the number of the parishioner that’s possessed, Enginn if the value is $0$ and Gunnar if the value is greater than $N$.
Explanation of Sample Inputs
In the first sample $N = 3$, $a = 1$, $b = 3$. If we calculate the XOR of all values from $1$ to $3$ we get $(1\textrm{ XOR }2)\textrm{ XOR }3 = 0$. Thus no one is possessed so the answer is Enginn.
In the second input $N = 7$, $a = 1$, $b = 4$. If we calculate the XOR of all numbers from $1$ to $4$ the result is $4$. Thus the fourth person on the list is possessed, so the answer is 4.
In the third sample $N = 6$, $a = 3$, $b = 4$. If we calculate the XOR of all numbers from $3$ to $4$ the result is $7$. Gunnar is thus possessed and the answer is Gunnar.
Scoring
The solution will be tested on input data of varying difficulty and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.
|
Group |
Points |
Constraints |
|
1 |
33 |
$ 1 \le N \le 1000$ |
|
2 |
33 |
$ 1 \le N \le 10^{18}$, $a = 1$ |
|
3 |
34 |
$ 1 \le N \le 10^{18}$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
5 1 3 |
Enginn |
| Sample Input 2 | Sample Output 2 |
|---|---|
7 1 4 |
4 |
| Sample Input 3 | Sample Output 3 |
|---|---|
6 3 4 |
Gunnar |
