{"raw_statement":[{"iden":"statement","content":"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).\n\nRoma 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:\n\n*   Initially Roma doesn't know the number of vertical and horizontal lines and their coordinates;\n*   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.\n\nUncle Anton is in a hurry to the UOI (Uzhlandian Olympiad in Informatics), so he can only answer no more than 3·105 questions.\n\nThe 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."},{"iden":"input","content":"There is no input initially. Your program should make queries to get information.\n\nIt is guaranteed that the number of horizontal and vertical lines is at least 1 and less than or equal to 104 for each type."},{"iden":"interaction","content":"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.\n\nYou can do no more than 3·105 queries.\n\nWhen you are ready to print the answer, print three lines:\n\n1.  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_).\n2.  In the second line print _n_ integers _x_1, _x_2, ..., _x__n_ — the coordinates of the vertical lines.\n3.  In the third line in the same format print _m_ integers _y_1, _y_2, ..., _y__m_ — the coordinates of the horizontal lines.\n\nYou can print coordinates in arbitrary order.\n\nTo make \"_flush_\", you can use (just after printing a query/answer and end-of-line):\n\n*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   see the documentation for other languages.\n\nYou will get _Wrong Answer_ if you make more queries than allowed or make an invalid query.\n\nYou can get _Idleness Limit Exceeded_ if you don't print anything or if you forget to flush the output.\n\nIf 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.\n\n**Making test for hacking**\n\nThe first line should contain two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 104).\n\nThe second line should contain _n_ distinct integers _x__i_ (-108 ≤ _x__i_ ≤ 108) — the coordinates of the vertical lines.\n\nThe third line should contain _m_ distinct integers _y__i_ (-108 ≤ _y__i_ ≤ 108) — the coordinates of the horizontal lines.\n\nYou can write coordinates in arbitrary order.\n\nYou can see the example case in the notes."},{"iden":"example","content":"Input\n\n1\n1\n3\n2\n\nOutput\n\n0 1 2\n0 -2 -2\n0 5 6\n0 -2 2\n1 1 2\n2\n0 -3"},{"iden":"note","content":"The example test is\n\n1 2\n2\n0 -3\n\nThe minimum distances are:\n\n*   from (1, 2) to _x_ = 2;\n*   from ( - 2,  - 2) to _y_ =  - 3;\n*   from (5, 6) to _x_ = 2;\n*   from ( - 2, 2) to _y_ = 0."}],"translated_statement":[{"iden":"input","content":"最初没有输入。你的程序需要通过提问来获取信息。保证水平线和垂直线的数量至少为 $1$，且每种类型不超过 $10^4$ 条。"},{"iden":"interaction","content":"要进行一次查询，请输出一行 \"_0 x y_\"（$-10^8 ≤ x, y ≤ 10^8$），其中 $x$ 和 $y$ 是点的坐标。每次查询后，你需要输出换行符，执行 \"_flush_\" 操作，然后读取该查询的答案 —— 该点到 Uzhlyandia 主直线的最小距离。你最多可以进行 $3·10^5$ 次查询。\n\n当你准备好输出答案时，请输出三行：\n\n在第一行输出 \"_1 n m_\"，其中 $n$ 是垂直线的数量（平行于 $OY$），$m$ 是水平线的数量（平行于 $OX$）。\n\n在第二行输出 $n$ 个整数 $x_1, x_2, ..., x_n$ —— 垂直线的坐标。\n\n在第三行以相同格式输出 $m$ 个整数 $y_1, y_2, ..., y_m$ —— 水平线的坐标。\n\n你可以以任意顺序输出坐标。\n\n要执行 \"_flush_\"，你可以在（输出查询/答案和换行符后）使用：\n\n_ fflush(stdout) _ 在 C++ 中；\n_ System.out.flush() _ 在 Java 中；\n_ stdout.flush() _ 在 Python 中；\n_ flush(output) _ 在 Pascal 中；\n请参阅其他语言的文档。\n\n如果你进行的查询次数超过限制或进行了无效查询，你会得到 _Wrong Answer_。\n\n如果你没有输出任何内容，或忘记刷新输出，你可能会得到 _Idleness Limit Exceeded_。\n\n如果在任何时候你的程序读到 $-1$ 作为答案，它应立即正常退出（例如，调用 _exit(0)_）。在这种情况下你会得到 _Wrong Answer_，这意味着你进行了超过允许次数的查询或进行了无效查询。如果你忽略这一点，你的程序将继续从已关闭的流中读取，可能导致其他错误 verdict。\n\n*制作用于 hack 的测试数据*\n\n第一行应包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 10^4$）。\n\n第二行应包含 $n$ 个互不相同的整数 $x_i$（$-10^8 ≤ x_i ≤ 10^8$）— 垂直线的坐标。\n\n第三行应包含 $m$ 个互不相同的整数 $y_i$（$-10^8 ≤ y_i ≤ 10^8$）— 水平线的坐标。\n\n你可以以任意顺序输出坐标。\n\n你可以参考注释中的示例情况。"},{"iden":"note","content":"示例测试是 1 2\n20 -3\n最小距离为：\n从 $ (1, 2) $ 到 $ x = 2 $；\n从 $ ( - 2,  - 2) $ 到 $ y =  - 3 $；\n从 $ (5, 6) $ 到 $ x = 2 $；\n从 $ ( - 2, 2) $ 到 $ y = 0 $。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\nLet $ V = \\{x_1, x_2, \\dots, x_n\\} $ be the set of vertical line coordinates ($ n \\leq 10^4 $), and $ H = \\{y_1, y_2, \\dots, y_m\\} $ be the set of horizontal line coordinates ($ m \\leq 10^4 $). All values are integers.\n\n**Given:**\n\n- The sets $ V $ and $ H $ are unknown.\n- For any query point $ (x, y) $, the response is:\n  $$\n  d(x, y) = \\min\\left( \\min_{v \\in V} |x - v|, \\min_{h \\in H} |y - h| \\right)\n  $$\n- You may make at most $ 3 \\cdot 10^5 $ queries.\n- The goal is to recover the sets $ V $ and $ H $.\n\n**Objective:**\n\nReconstruct the sets $ V $ and $ H $ using adaptive queries of the form $ (x, y) $, each returning $ d(x, y) $, within the query limit.\n\n**Constraints:**\n\n- $ 1 \\leq n, m \\leq 10^4 $\n- $ -10^8 \\leq x_i, y_i \\leq 10^8 $\n- All coordinates are integers.\n- All values in $ V $ and $ H $ are distinct.\n\n**Output:**\n\nPrint the recovered sets $ V $ and $ H $, each on a separate line, in arbitrary order.","simple_statement":null,"has_page_source":false}