Problem C
Mario or Luigi

Mario and Luigi are playing a game where they pick distinct numbers $M, L$ ($0 \leq M,L < 2^{10^{18}}$). In order to place careful bets on the outcome of the game, you wish to know whose number is larger. Both Mario and Luigi have already shared their secret numbers with their close friend Toadette, who has memorized both of their numbers as binary numbers with $10^{18}$ digits. So, you decide to go to Toadette for help!

Fortunately, Toadette is willing to help you, and lets you ask her questions of one of two following types:

1. Give two integers $a$ and $b$, and ask “If you write out $M$ and $L$ in binary, are $M$’s bits in the (inclusive) range $[a,b]$ equal to $L$’s bits in the same range?” Toadette responds “YES” or “NO”.

2. Give an integer $x$, and ask “Is the $x$’th bit of $M$ or $L$ greater?” Toadette responds with “MARIO”, “LUIGI”, or “EQUAL”.

However, Toadette is afraid that her answers to questions of the first type gives you too much information, so she decides to make things interesting. Each time you ask a question of the first type, she will lie to you (independently and randomly) with probability $\frac{1}{13}$. Can you find out whose number is larger by asking at most 192 questions?

Interaction

This is an interactive problem. You will interact with Toadette using standard input and output. You may ask at most $192$ questions.

To ask a question, write a line to standard output in one of the following formats:

• “1 a b” ($0 \leq a \leq b < 10^{18}$) – If you write out $M$ and $L$ in binary, are the bits in the range $[a, b]$ for $M$ and $L$ equal? Toadette will respond with either “YES” or “NO”.

• “2 x” ($0 \leq x < 10^{18}$) – In whose number is the $x$-th bit greater? Toadette will respond with “MARIO” or “LUIGI” depending on whose number has the larger bit, or “EQUAL” if the bits in that position are the same.

To guess whose number is larger, write a line to standard output in the following format:

• “! S” ($S \in \{ \texttt{MARIO}, \texttt{LUIGI}\} $) – Guess that $S$’s number is larger.

You are allowed to make only one guess, and your program must terminate after making the guess. Note that guessing whose number is larger does not count towards your limit of 192 questions.

Note: Toadette views the least significant (rightmost) bit as the bit with index $0$, and the most significant (leftmost) bit as the bit with index $10^{18} - 1$. For example, considering the number $356$ ($0\ldots 0101100100$ in binary), the range $[0,3]$ would correspond to the rightmost four digits $0100$.

After every question, make sure to output a newline character and flush the output stream. To do this, use:

• fflush(stdout) in C;

• cout.flush() in C++;

• System.out.flush() in Java;

• stdout.flush() in Python.

Judging

Submissions will be judged on exactly $100$ testcases. The numbers $M$ and $L$ for each game may or may not be generated randomly, and can differ between submissions. For each question of the first type, Toadette’s decision to lie or not will be determined randomly and thus will change between submissions.

1 0 4

NO

2 3

MARIO

! MARIO