{"raw_statement":[{"iden":"statement","content":"_This is an interactive problem._\n\nYou are given a **sorted** in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to _x_.\n\nMore formally, there is a singly liked list built on an array of _n_ elements. Element with index _i_ contains two integers: _value__i_ is the integer value in this element, and _next__i_ that is the index of the next element of the singly linked list (or _\\-1_, if the current element is the last). The list is sorted, i.e. if _next__i_ ≠  - 1, then _value__next__i_ > _value__i_.\n\nYou are given the number of elements in the list _n_, the index of the first element _start_, and the integer _x_.\n\nYou can make up to 2000 queries of the following two types:\n\n*   _? i_ (1 ≤ _i_ ≤ _n_) — ask the values _value__i_ and _next__i_,\n*   _! ans_ — give the answer for the problem: the minimum integer, greater than or equal to _x_, or _! -1_, if there are no such integers. Your program should terminate after this query.\n\nWrite a program that solves this problem."},{"iden":"input","content":"The first line contains three integers _n_, _start_, _x_ (1 ≤ _n_ ≤ 50000, 1 ≤ _start_ ≤ _n_, 0 ≤ _x_ ≤ 109) — the number of elements in the list, the index of the first element and the integer _x_."},{"iden":"output","content":"To print the answer for the problem, print _! ans_, where _ans_ is the minimum integer in the list greater than or equal to _x_, or _\\-1_, if there is no such integer."},{"iden":"interaction","content":"To make a query of the first type, print _? i_ (1 ≤ _i_ ≤ _n_), where _i_ is the index of element you want to know information about.\n\nAfter each query of type _?_ read two integers _value__i_ and _next__i_ (0 ≤ _value__i_ ≤ 109,  - 1 ≤ _next__i_ ≤ _n_, _next__i_ ≠ 0).\n\nIt is guaranteed that if _next__i_ ≠  - 1, then _value__next__i_ > _value__i_, and that the array values give a valid singly linked list with _start_ being the first element.\n\nNote that you can't ask more than 1999 queries of the type _?_.\n\nIf _next__i_ =  - 1 and _value__i_ =  - 1, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling _exit(0)_). You will receive \"_Wrong Answer_\", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.\n\nYour solution will get \"Idleness Limit Exceeded\", if you don't print anything or forget to _flush_ the output, including the final answer.\n\nTo _flush_ you can use (just after printing a query and 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 three integers _n_, _start_, _x_ (1 ≤ _n_ ≤ 50000, 1 ≤ _start_ ≤ _n_, 0 ≤ _x_ ≤ 109).\n\nIn the next _n_ lines print the description of the elements of the list: in the _i_\\-th line print two integers _value__i_ and _next__i_ (0 ≤ _value__i_ ≤ 109,  - 1 ≤ _next__i_ ≤ _n_, _next__i_ ≠ 0).\n\nThe printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from _start_ by following links _next__i_, and the last element _end_ should have _\\-1_ in the _next__end_."},{"iden":"example","content":"Input\n\n5 3 80\n97 -1\n58 5\n16 2\n81 1\n79 4\n\nOutput\n\n? 1\n? 2\n? 3\n? 4\n? 5\n! 81"},{"iden":"note","content":"You can read more about singly linked list by the following link: [https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list](https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list)\n\n<center>The illustration for the first sample case. Start and finish elements are marked dark. ![image](https://espresso.codeforces.com/5fdcc2f8a535c08a9221d03d7e527af8267838c0.png)\n\n</center>"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"_This is an interactive problem._\\n\\nYou are given a *sorted* in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to $x$.\\n\\nMore formally, there is a singly linked list built on an array of $n$ elements. Element with index $i$ contains two integers: $value_i$ is the integer value in this element, and $next_i$ that is the index of the next element of the singly linked list (or $-1$, if the current element is the last). The list is sorted, i.e. if $next_i ≠  - 1$, then $value_{next_i} > value_i$.\\n\\nYou are given the number of elements in the list $n$, the index of the first element $start$, and the integer $x$.\\n\\nYou can make up to $2000$ queries of the following two types:\\n\\nWrite a program that solves this problem.\\n\\nThe first line contains three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$) — the number of elements in the list, the index of the first element and the integer $x$.\\n\\nTo print the answer for the problem, print _! ans_, where _ans_ is the minimum integer in the list greater than or equal to $x$, or _-1_, if there is no such integer.\\n\\nTo make a query of the first type, print _? i_ ($1 ≤ i ≤ n$), where _i_ is the index of element you want to know information about.\\n\\nAfter each query of type _?_ read two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$).\\n\\nIt is guaranteed that if $next_i ≠  - 1$, then $value_{next_i} > value_i$, and that the array values give a valid singly linked list with $start$ being the first element.\\n\\nNote that you can't ask more than $1999$ queries of the type _?_.\\n\\nIf $next_i =  - 1$ and $value_i =  - 1$, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling _exit(0)_). You will receive \\\"_Wrong Answer_\\\", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream.\\n\\nYour solution will get \\\"Idleness Limit Exceeded\\\", if you don't print anything or forget to _flush_ the output, including the final answer.\\n\\nTo _flush_ you can use (just after printing a query and line end):\\n\\n#cf_span(class=[], body=[*Hacks format*])\\n\\nFor hacks, use the following format:\\n\\nIn the first line print three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$).\\n\\nIn the next $n$ lines print the description of the elements of the list: in the $i$-th line print two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$).\\n\\nThe printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from $start$ by following links $next_i$, and the last element $end$ should have $-1$ in the $next_{end}$.\\n\\nYou can read more about singly linked list by the following link: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list \\n\\nThe illustration for the first sample case. Start and finish elements are marked dark. \\n\"},{\"iden\":\"input\",\"content\":\"The first line contains three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$) — the number of elements in the list, the index of the first element and the integer $x$.\"},{\"iden\":\"output\",\"content\":\"To print the answer for the problem, print _! ans_, where _ans_ is the minimum integer in the list greater than or equal to $x$, or _-1_, if there is no such integer.\"},{\"iden\":\"interaction\",\"content\":\"To make a query of the first type, print _? i_ ($1 ≤ i ≤ n$), where _i_ is the index of element you want to know information about. After each query of type _?_ read two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$). It is guaranteed that if $next_i ≠  - 1$, then $value_{next_i} > value_i$, and that the array values give a valid singly linked list with $start$ being the first element. Note that you can't ask more than $1999$ queries of the type _?_. If $next_i =  - 1$ and $value_i =  - 1$, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling _exit(0)_). You will receive \\\"_Wrong Answer_\\\", it means that you asked more queries than allowed, or asked an invalid query. If you ignore this, you can get other verdicts since your program will continue to read from a closed stream. Your solution will get \\\"Idleness Limit Exceeded\\\", if you don't print anything or forget to _flush_ the output, including the final answer. To _flush_ you can use (just after printing a query and line end):  _fflush(stdout)_ in C++;  _System.out.flush()_ in Java;  _stdout.flush()_ in Python;  _flush(output)_ in Pascal;  For other languages see documentation. #cf_span(class=[], body=[*Hacks format*]) For hacks, use the following format: In the first line print three integers $n$, $start$, $x$ ($1 ≤ n ≤ 50000$, $1 ≤ start ≤ n$, $0 ≤ x ≤ 10^9$). In the next $n$ lines print the description of the elements of the list: in the $i$-th line print two integers $value_i$ and $next_i$ ($0 ≤ value_i ≤ 10^9$, $-1 ≤ next_i ≤ n$, $next_i ≠ 0$). The printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from $start$ by following links $next_i$, and the last element $end$ should have $-1$ in the $next_{end}$.\"},{\"iden\":\"note\",\"content\":\"You can read more about singly linked list by the following link: https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list The illustration for the first sample case. Start and finish elements are marked dark. \"}]}","sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of elements in the list.  \nLet $ \\text{start} \\in \\{1, \\dots, n\\} $ be the index of the first element.  \nLet $ x \\in \\mathbb{Z}_{\\geq 0} $ be the target value.  \n\nLet $ V: \\{1, \\dots, n\\} \\to \\mathbb{Z}_{\\geq 0} $ be the value function, where $ V(i) $ is the integer stored at index $ i $.  \nLet $ N: \\{1, \\dots, n\\} \\to \\{-1\\} \\cup \\{1, \\dots, n\\} $ be the next-pointer function, where $ N(i) $ is the index of the next element, or $-1$ if $ i $ is the last.  \n\nThe list is sorted: for all $ i \\in \\{1, \\dots, n\\} $, if $ N(i) \\neq -1 $, then $ V(N(i)) > V(i) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50000 $  \n2. $ 1 \\leq \\text{start} \\leq n $  \n3. $ 0 \\leq x \\leq 10^9 $  \n4. At most $ 1999 $ queries of type $ ?\\ i $ are allowed.  \n5. For all $ i \\in \\{1, \\dots, n\\} $, $ V(i) \\geq 0 $, and $ N(i) \\neq 0 $.  \n\n**Objective**  \nFind the minimum value $ v \\in \\{V(i) \\mid i \\in \\{1, \\dots, n\\}\\} $ such that $ v \\geq x $.  \nIf no such $ v $ exists, return $ -1 $.  \n\n**Query Interface**  \nYou may query index $ i \\in \\{1, \\dots, n\\} $ via `? i`, and receive $ (V(i), N(i)) $.  \nYou must output the answer via `! ans`, where $ \\text{ans} \\in \\{-1\\} \\cup \\{V(i) \\mid i \\in \\{1, \\dots, n\\}\\} $ and $ \\text{ans} \\geq x $ or $ \\text{ans} = -1 $.","simple_statement":null,"has_page_source":false}