# Practice on Toph

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

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

Neo has a hidden array **A** of **n** integers where **0 ≤ A _{i} ≤ 10^{9}** is satisfied for each

**1 l r**, Neo will tell you the bitwise OR of all**A**such that_{i}**l ≤ i ≤ r**.**2 l r**, Neo will tell you the bitwise XOR of all**A**such that_{i}**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

**A**⊕_{1}**A**⊕ … ⊕_{2}**A**>_{k}**A**⊕_{k+1}**A**⊕ … ⊕_{k+2}**A**, where ⊕ is the bitwise XOR operator._{n}

The input starts with a line containing an integer **n (1 ≤ n ≤ 10 ^{5})** — the length of the array. Your program should read it at first.

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;

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