Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

XOR Partition

By YouKnowWho · Limits 1s, 512 MB · Interactive

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

  • A1A2 ⊕ … ⊕ Ak > Ak+1Ak+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:

> 3
< 1 1 1
> 3
< 2 2 2
> 1
< 1 3 3
> 1
< ! 1

> 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:

> 2
< 2 1 1
> 7
< 2 2 2
> 7
< ! -1

Discussion
Statistics

79% Solution Ratio

kzvd4729Earliest, 1M ago

kzvd4729Fastest, 0.0s

kzvd4729Lightest, 131 kB

kzvd4729Shortest, 654B

Submit

Login to submit