{"raw_statement":[{"iden":"statement","content":"**This is an interactive problem.**\n\nVasya and Vitya play a game. Vasya thought of two integers $a$ and $b$ from $1$ to $n$ and Vitya tries to guess them. Each round he tells Vasya two numbers $x$ and $y$ from $1$ to $n$. If both $x=a$ and $y=b$ then Vitya wins. Else Vasya must say one of the three phrases:\n\n1.  $x$ is less than $a$;\n2.  $y$ is less than $b$;\n3.  $x$ is greater than $a$ or $y$ is greater than $b$.\n\nVasya can't lie, but if multiple phrases are true, he may choose any of them. For example, if Vasya thought of numbers $2$ and $4$, then he answers with the phrase $3$ to a query $(3, 4)$, and he can answer with the phrase $1$ or phrase $3$ to a query $(1, 5)$.\n\nHelp Vitya win in no more than $600$ rounds."},{"iden":"input","content":"The first line contains a single integer $n$ ($1 \\leq n \\leq 10^{18}$) — the upper limit of the numbers."},{"iden":"interaction","content":"First, you need to read the number $n$, after that you can make queries.\n\nTo make a query, print two integers: $x$ and $y$ ($1 \\leq x, y \\leq n$), then _flush_ the output.\n\nAfter each query, read a single integer $ans$ ($0 \\leq ans \\leq 3$).\n\nIf $ans > 0$, then it is the number of the phrase said by Vasya.\n\nIf $ans = 0$, it means that you win and your program should terminate.\n\nIf you make more than $600$ queries or make an incorrect query, you will get _Wrong Answer_.\n\nYour solution will get _Idleness Limit Exceeded_, if you don't print anything or forget to _flush_ the output.\n\nTo _flush_ you need to do the following right after printing a query and a line end:\n\n*   _fflush(stdout)_ in C++;\n*   _System.out.flush()_ in Java;\n*   _stdout.flush()_ in Python;\n*   _flush(output)_ in Pascal;\n*   For other languages see documentation.\n\n**Hacks format**\n\nFor hacks, use the following format:\n\nIn the first line, print a single integer $n$ ($1 \\leq n \\leq 10^{18}$) — the upper limit of the numbers.\n\nIn the second line, print two integers $a$ and $b$ ($1 \\leq a, b \\leq n$) — the numbers which Vasya thought of.\n\nIn the third line, print a single integer $m$ ($1 \\leq m \\leq 10^5$) — the number of instructions for the interactor.\n\nIn each of the next $m$ lines, print five integers: $x_i$, $y_i$, $r^{12}_i$, $r^{13}_i$, and $r^{23}_i$ ($1 \\leq x_i, y_i \\leq n$), where $r^{ST}_i$ equals to either number $S$ or number $T$.\n\nWhile answering the query $x\\,\\, y$, the interactor finds a number $i$ from $1$ to $n$ with the minimal value $|x-x_i| + |y-y_i|$. If multiple numbers can be chosen, the least $i$ is preferred. Then the interactor answers to the query, but if there are two phrases $S$ and $T$ that can be given, then $r^{ST}_i$ is chosen.\n\nFor example, the sample test data file contains the following:\n\n5\n2 4\n2\n2 5 1 1 2\n4 1 2 3 3"},{"iden":"example","content":"Input\n\n5\n3\n3\n2\n1\n0\n\nOutput\n\n4 3\n3 4\n3 3\n1 5\n2 4"},{"iden":"note","content":"Let's analyze the sample test. The chosen numbers are $2$ and $4$. The interactor was given two instructions.\n\nFor the query $(4, 3)$, it can return $2$ or $3$. Out of the two instructions the second one is chosen, so the interactor returns $a^{23}_2=3$.\n\nFor the query $(3, 4)$, it can return only $3$.\n\nFor the query $(3, 3)$, it can return $2$ or $3$. Out of the two instructions the first one is chosen (since in case of equal values, the least number is preferred), so the interactor returns $a^{23}_1=2$.\n\nFor the query $(1, 5)$, it can return $1$ or $3$. Out of the two instructions the first one is chosen, so the interactor returns $a^{13}_1=1$.\n\nIn the fifth query $(2, 4)$, the numbers are guessed correctly, the player wins."}],"translated_statement":[{"iden":"statement","content":"*这是一个交互式问题。*\n\nVasya 和 Vitya 玩一个游戏。Vasya 想了两个整数 $a$ 和 $b$，范围在 $1$ 到 $n$ 之间，Vitya 试图猜出它们。每一轮，他告诉 Vasya 两个数 $x$ 和 $y$，范围也在 $1$ 到 $n$ 之间。如果 $x = a$ 且 $y = b$，则 Vitya 获胜。否则，Vasya 必须说出以下三个短语之一：\n\nVasya 不能说谎，但如果多个短语都为真，他可以选择其中任意一个。例如，如果 Vasya 想的数是 $2$ 和 $4$，那么对于查询 $(3, 4)$，他会回答短语 $3$；对于查询 $(1, 5)$，他可以回答短语 $1$ 或短语 $3$。\n\n帮助 Vitya 在不超过 $600$ 轮内获胜。\n\n第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n首先，你需要读取数字 $n$，之后你可以进行查询。\n\n要进行一次查询，输出两个整数：$x$ 和 $y$ ($1 lt.eq x, y lt.eq n$)，然后 _刷新_ 输出。\n\n每次查询后，读取一个整数 $ans$ ($0 lt.eq ans lt.eq 3$)。\n\n如果 $ans > 0$，则表示 Vasya 说出的短语编号。\n\n如果 $ans = 0$，表示你猜中了，你的程序应终止。\n\n如果你进行了超过 $600$ 次查询或进行了无效查询，你将获得 _错误答案_。\n\n如果你没有输出任何内容或忘记 _刷新_ 输出，你的程序将获得 _空闲超时_。\n\n要在打印查询和换行后 _刷新_ 输出，你需要执行以下操作：\n\n*黑客格式*\n\n对于黑客输入，使用以下格式：\n\n第一行，输出一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n第二行，输出两个整数 $a$ 和 $b$ ($1 lt.eq a, b lt.eq n$) —— Vasya 想的两个数。\n\n第三行，输出一个整数 $m$ ($1 lt.eq m lt.eq 10^5$) —— 交互器的指令数量。\n\n接下来的 $m$ 行，每行输出五个整数：$x_i$、$y_i$、$r^(12)_i$、$r^(13)_i$ 和 $r^(23)_i$ ($1 lt.eq x_i, y_i lt.eq n$)，其中 $r^(S T)_i$ 等于数字 $S$ 或 $T$。\n\n当回答查询 $x \\; y$ 时，交互器寻找满足 $| x -x_i | + | y -y_i |$ 最小的编号 $i$（从 $1$ 到 $n$）。如果有多个这样的 $i$，则选择最小的 $i$。然后交互器根据该指令回答查询；但如果存在两个可选短语 $S$ 和 $T$，则选择 $r^(S T)_i$。\n\n例如，样例测试数据文件包含以下内容：\n\n让我们分析样例测试。所选数字是 $2$ 和 $4$。交互器被给予两条指令。\n\n对于查询 $(4, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第二条，因此交互器返回 $a^(23)_2 = 3$。\n\n对于查询 $(3, 4)$，它只能返回 $3$。\n\n对于查询 $(3, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第一条（因为当值相等时优先选择编号最小的），因此交互器返回 $a^(23)_1 = 2$。\n\n对于查询 $(1, 5)$，它可以返回 $1$ 或 $3$。在两条指令中选择第一条，因此交互器返回 $a^(13)_1 = 1$。\n\n在第五次查询 $(2, 4)$ 时，数字被正确猜出，玩家获胜。\n\n"},{"iden":"input","content":"第一行包含一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。"},{"iden":"interaction","content":"首先，你需要读取数字 $n$，之后你可以进行查询。要进行一次查询，输出两个整数：$x$ 和 $y$ ($1 lt.eq x, y lt.eq n$)，然后 _刷新_ 输出。每次查询后，读取一个整数 $ans$ ($0 lt.eq ans lt.eq 3$)。如果 $ans > 0$，则表示 Vasya 说出的短语编号。如果 $ans = 0$，表示你猜中了，你的程序应终止。如果你进行了超过 $600$ 次查询或进行了无效查询，你将获得 _错误答案_。如果你没有输出任何内容或忘记 _刷新_ 输出，你的程序将获得 _空闲超时_。要在打印查询和换行后 _刷新_ 输出，你需要执行以下操作：\n\n_fflush(stdout)_ 在 C++ 中；\n_System.out.flush()_ 在 Java 中；\n_stdout.flush()_ 在 Python 中；\n_flush(output)_ 在 Pascal 中；\n其他语言请参阅文档。\n\n*黑客格式*\n\n对于黑客输入，使用以下格式：\n\n第一行，输出一个整数 $n$ ($1 lt.eq n lt.eq 10^(18)$) —— 数字的上限。\n\n第二行，输出两个整数 $a$ 和 $b$ ($1 lt.eq a, b lt.eq n$) —— Vasya 想的两个数。\n\n第三行，输出一个整数 $m$ ($1 lt.eq m lt.eq 10^5$) —— 交互器的指令数量。\n\n接下来的 $m$ 行，每行输出五个整数：$x_i$、$y_i$、$r^(12)_i$、$r^(13)_i$ 和 $r^(23)_i$ ($1 lt.eq x_i, y_i lt.eq n$)，其中 $r^(S T)_i$ 等于数字 $S$ 或 $T$。\n\n当回答查询 $x \\; y$ 时，交互器寻找满足 $| x -x_i | + | y -y_i |$ 最小的编号 $i$（从 $1$ 到 $n$）。如果有多个这样的 $i$，则选择最小的 $i$。然后交互器根据该指令回答查询；但如果存在两个可选短语 $S$ 和 $T$，则选择 $r^(S T)_i$。\n\n例如，样例测试数据文件包含以下内容：\n\n5\n2 4\n2\n2 5 1 1 2\n4 1 2 3 3"},{"iden":"note","content":"让我们分析样例测试。所选数字是 $2$ 和 $4$。交互器被给予两条指令。\n\n对于查询 $(4, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第二条，因此交互器返回 $a^(23)_2 = 3$。\n\n对于查询 $(3, 4)$，它只能返回 $3$。\n\n对于查询 $(3, 3)$，它可以返回 $2$ 或 $3$。在两条指令中选择第一条（因为当值相等时优先选择编号最小的），因此交互器返回 $a^(23)_1 = 2$。\n\n对于查询 $(1, 5)$，它可以返回 $1$ 或 $3$。在两条指令中选择第一条，因此交互器返回 $a^(13)_1 = 1$。\n\n在第五次查询 $(2, 4)$ 时，数字被正确猜出，玩家获胜。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 10^{18} $, be the upper bound.  \nLet $ (a, b) \\in \\{1, \\dots, n\\}^2 $ be the hidden pair, unknown to the solver.  \n\n**Query Response Rules**  \nFor any query $ (x, y) \\in \\{1, \\dots, n\\}^2 $:  \n- If $ x = a $ and $ y = b $, respond with $ 0 $ (win).  \n- Otherwise, respond with $ ans \\in \\{1, 2, 3\\} $, where:  \n  - $ ans = 1 $ if $ x = a $ and $ y \\neq b $,  \n  - $ ans = 2 $ if $ x \\neq a $ and $ y = b $,  \n  - $ ans = 3 $ if $ x \\neq a $ and $ y \\neq b $.  \nIf multiple conditions hold, any valid $ ans $ may be chosen.  \n\n**Constraints**  \n- At most $ 600 $ queries allowed.  \n- All queries must satisfy $ 1 \\leq x, y \\leq n $.  \n\n**Objective**  \nDetermine $ (a, b) $ using at most $ 600 $ adaptive queries, each followed by reading the response $ ans \\in \\{0, 1, 2, 3\\} $, and terminate upon receiving $ ans = 0 $.","simple_statement":null,"has_page_source":false}