XOR Partition
Neo has a hidden array A of n integers where 0 ≤ Ai ≤ 109 is satisfied for each i from 1 to n . You can ask queries of the following 2 types
1 l r, Neo will tell you the bitwise OR of all Ai such that l ≤ i ≤ r.
2 l r, Neo will tell you the bitwise XOR of all Ai such that l ≤ i ≤ r.
You can ask at most 32 queries. You need to find the minimum index k(1 ≤ k ≤ n-1) such that the following condition is satisfied
- A1 ⊕ A2 ⊕ ... ⊕ Ak > Ak+1 ⊕ Ak+2 ⊕ ... ⊕ An, where ⊕ is the bitwise XOR operator.
Input
The input starts with a line containing an integer n (1 ≤ n ≤ 105) — the length of the array. Your program should read it at first.
Interaction
To ask a query use the format "1 l r" (without quotes), (1 ≤ l ≤ r ≤ n) or "2 l r" (without quotes), (1 ≤ l ≤ r ≤ n). Don't forget to print a newline after each query!
After printing the query your program should read a single integer, the answer from Neo.
You can use at most 32 queries. If you ask more than 32 queries or at least one incorrect query, your solution can get any verdict except "Accepted".
Don't forget to flush the output after printing a query!
To flush you can use (just after printing new line):
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
Output
To print the final answer, print "! k"(without quotes), where (1 ≤ k ≤ n-1) and k is the minimum index that satisfies the aforementioned condition. If there is no k which satisfies the condition print "! -1"(without quotes). Don't forget to flush the output after printing the answer! Note that this final query is not counted when considering the total number of queries you've asked.
A sample interaction for the array A=[3, 1, 1] may look like following:
> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.
Another sample interaction for the array A=[7, 7] may look like following: