Finding lines
Contest: Codeforces Round 407 (Div. 1)
Difficulty rating: 3000
Tags: constructive algorithms, divide and conquer, interactive

After some programming contest Roma decided to try himself in tourism. His home country Uzhlyandia is a Cartesian plane. He wants to walk along each of the Main Straight Lines in Uzhlyandia. It is known that each of these lines is a straight line parallel to one of the axes (i.e. it is described with the equation x = a or y = a, where a is integer called the coordinate of this line).

Roma lost his own map, so he should find out the coordinates of all lines at first. Uncle Anton agreed to help him, using the following rules:

- Initially Roma doesn't know the number of vertical and horizontal lines and their coordinates;
- Roma can announce integer coordinates of some point in Uzhlandia, and Anton then will tell him the minimum among the distances from the chosen point to each of the lines. However, since the coordinates of the lines don't exceed 108 by absolute value, Roma can't choose a point with coordinates exceeding 108 by absolute value.

Uncle Anton is in a hurry to the UOI (Uzhlandian Olympiad in Informatics), so he can only answer no more than 3·105 questions.

The problem is that Roma doesn't know how to find out the coordinates of the lines. Write a program that plays Roma's role and finds the coordinates.

Input format:
There is no input initially. Your program should make queries to get information.

It is guaranteed that the number of horizontal and vertical lines is at least 1 and less than or equal to 104 for each type.

Interaction format:
To make a query, print a line "0 x y" (-108 ≤ x, y ≤ 108), where x and y are the coordinates of the point. After each query you need to print end-of-line, make "flush" operation, and then read the answer to the query — the minimum among the distances prom this point to the Main Straight Lines of Uzhlyandia.

You can do no more than 3·105 queries.

When you are ready to print the answer, print three lines:

1. In the first line print "1 n m", where n is the number of vertical lines (parallel to OY), and m is the number of horizontal lines (parallel to OX).
2. In the second line print n integers x1, x2, ..., xn — the coordinates of the vertical lines.
3. In the third line in the same format print m integers y1, y2, ..., ym — the coordinates of the horizontal lines.

You can print coordinates in arbitrary order.

To make "flush", you can use (just after printing a query/answer and end-of-line):

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- see the documentation for other languages.

You will get Wrong Answer if you make more queries than allowed or make an invalid query.

You can get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output.

If at any moment your program reads -1 as an answer, it should immediately exit normally (for example, by calling exit(0)). You will get Wrong Answer in this case, it means that you made more queries than allowed, or made an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.

Making test for hacking

The first line should contain two integers n and m (1 ≤ n, m ≤ 104).

The second line should contain n distinct integers xi (-108 ≤ xi ≤ 108) — the coordinates of the vertical lines.

The third line should contain m distinct integers yi (-108 ≤ yi ≤ 108) — the coordinates of the horizontal lines.

You can write coordinates in arbitrary order.

You can see the example case in the notes.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
The example test is

The minimum distances are:

- from (1, 2) to x = 2;
- from ( - 2,  - 2) to y =  - 3;
- from (5, 6) to x = 2;
- from ( - 2, 2) to y = 0.

Example input:
1
1
3
2

Example output:
0 1 2
0 -2 -2
0 5 6
0 -2 2
1 1 2
2
0 -3

Editorial:
First we solve another problem. Let we have points not straight lines, but points on one axis. Let MAX = 108, that is, the maximum coordinate. First, we find the left and right points. The left is ( - MAX + get( - MAX)), and the right one (MAX - get(MAX)). Then we solve the problem recursively. There will be a function f(l, r) that finds all points on the segment (l, r) if l and r — are points. We have already found the extreme points, so we can call this function.
The function f(l, r) makes a query at the center point between l and r, that is, $${ \frac { 1 + r } { 2 } }$$. If the answer is equal to the distance to the extreme points, then there are no more points between l and r. If the distance is less, then for one more query we can find out the point on the left or right. Let this point x, then we start f(l, x) and f(x, r).
We introduce a function that checks if there is a vertical line x. We can select a random point in the range [ - MAX, MAX] and make a query, if the answer 0 — is a straight line. If MAX = 108, and the maximum n = 104, then the error probability is 10 - 4, if you querys twice, then 10 - 8.
Now we will solve the main task. We make a query at the point ( - MAX,  - MAX), we can find out whether the minimum distance to the vertical or horizontal line. We introduce the function G(x, y), which will find the nearest straight line whose coordinates are greater than x or y, and get(x, y) = 0. How is this solved? If there are no more lines, then for non-negative t, get(x + t, y + t) = t. Then we can find a minimal power such that get(x + t, y + t) ≠ t. Then we know that this applies to either the vertical line (x + t + get(x + t, y + t)), or the horizontal (y + t + get(x + t, y + t)) . We can find out which one. If, for example, to the vertical one, then we solve the problem for G(x + t + get(x + t, y + t), y).
Then we find either all horizontal lines, or all vertical lines. To find out which straight lines we found, we need to look at the last function G(x, y), namely our "ray". If it rests on the vertical straight MAX, then we find all the vertical ones. And vice versa.
Now how to find other lines. Let's say we found all the vertical ones. Then we will find the maximum distance between the neighbors, between the first line and ( - MAX), between the last line and (MAX), this distance will be at least $$\frac{MAX}{MAXN}$$.
That is, we search in what position the maximum will be reached, if there are no horizontal lines, let it be val. Let this be the coordinate x, we will make queries on the line x, starting with —  - MAX, ending with MAX, with the step $$\frac{val}{4}$$. We find all the points whose answer is not equal to val. Then we can divide all these points into "segments", that is, a set of points that go successively. For each "segment", the minimum distance will only apply to horizontal lines, that is, vertical ones will not affect in any way. Therefore, each "segment" can be solved independently, by the method already known to us (assume that there are no vertical lines).