Practice on Toph

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

The Lone Wolf

By farhanhasin · Limits 1s, 512 MB · Interactive

Just like you, the Lone Wolf is a loner and amidst a row of soulmates at Dhanmondi Lake today, only he's alone. In this unfair world, each person has a soulmatesheep value. Two persons' soulmatesheep values are equal if and only if they are soulmates. That means, Sadly, there's no other person having the same soulmatesheep value as the Lone Wolf and hence the desolation.

In total, there are N persons in the row, and they are sitting from left to right in a non-decreasing order of their soulmatesheep values. More than two persons can't be soulmates so no value will occur more than twice and one value will occur exactly once. Outside the row, there's this Badamwala. You can ask the Badamwala about any contiguous segment of people in the row, and he'll answer you with the bitwise XOR of the solumatesheep values of all the persons in that segment. You have to find the value and position of the Lone Wolf without asking the Badamwala too many questions as today is his busy day.

Input

Input begins with an integer N (1 ≤ N ≤ 100000), the number of persons in the row. Then, you can start the interaction. The indexing in the row is 1-based and soul values are integers between 1 to 109 inclusive. In every test case the numbers are fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.

You can make two types of interactions with the Badamwala:

0 L R: Here, L and R (1 ≤ L ≤ R ≤N) are the positions of respectively the first and the last person in the segment you want to ask about. For each of these queries, the Badamwala will answer you with the bit-wise XOR of the values of all the persons in that range. You cannot make this type of interaction more than 20 times. If you ask more queries, you will receive “Wrong Answer” as the verdict.

1 X V: Here, X and V are respectively the value and the position of the Lone Wolf. You have to make exactly one interaction of this type and this interaction will terminate the execution. So, after this interaction, you will not receive any reply from the Badamwala. Now, if X and V are correct then you will get “Accepted” as the verdict. Otherwise, you will receive “Wrong Answer”.

For invalid interactions, you may receive “Wrong Answer” or "CPU Limit Exceeded".

Output

The second type of interaction that you can have only once is considered as the output of your program.

Let's say the queue looks like this : [1, 1, 2, 2, 3, 4, 4]. So the Lone Wolf has value 3 and is at position 5. Here is what an example interaction would look like:

> 7
0 1 4
> 0
0 5 7
> 1
0 5 5
> 3
0 6 6
> 4
0 7 7
> 4
0 4 4
> 2
1 3 5

Discussion

Statistics


69% Solution Ratio

tmwilliamlin168Earliest, Feb '20

tmwilliamlin168Fastest, 0.0s

tmwilliamlin168Lightest, 131 kB

chieloShortest, 356B

Submit

Login to submit

Editorial

We can find out the lone wolf's solumatesheep value in a single query: 0 1 N as the other numbers wi...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.