{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThis is an interactive problem.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eYou are given a \u003cspan class\u003d\"tex-font-style-bf\"\u003esorted\u003c/span\u003e in increasing order singly linked list. You should find the minimum integer in the list which is greater than or equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eMore formally, there is a singly liked list built on an array of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e elements. Element with index \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e contains two integers: \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the integer value in this element, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e that is the index of the next element of the singly linked list (or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e, if the current element is the last). The list is sorted, i.e. if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ - 1\u003c/span\u003e, then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/sub\u003e \u0026gt; \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eYou are given the number of elements in the list \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, the index of the first element \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estart\u003c/i\u003e\u003c/span\u003e, and the integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eYou can make up to \u003cspan class\u003d\"tex-span\"\u003e2000\u003c/span\u003e queries of the following two types:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e? i\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;— ask the values \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003e! ans\u003c/span\u003e\u0026nbsp;— give the answer for the problem: the minimum integer, greater than or equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003e! -1\u003c/span\u003e, if there are no such integers. Your program should terminate after this query. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eWrite a program that solves this problem.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estart\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 50000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003estart\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ex\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;— the number of elements in the list, the index of the first element and the integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eTo print the answer for the problem, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e! ans\u003c/span\u003e, where \u003cspan class\u003d\"tex-font-style-tt\"\u003eans\u003c/span\u003e is the minimum integer in the list greater than or equal to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e, or \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e, if there is no such integer.\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eTo make a query of the first type, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e? i\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ei\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e), where \u003cspan class\u003d\"tex-font-style-tt\"\u003ei\u003c/span\u003e is the index of element you want to know information about.\u003c/p\u003e\u003cp\u003eAfter each query of type \u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e read two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e - 1 ≤ \u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ 0\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eIt is guaranteed that if \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ - 1\u003c/span\u003e, then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/sub\u003e \u0026gt; \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, and that the array values give a valid singly linked list with \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estart\u003c/i\u003e\u003c/span\u003e being the first element.\u003c/p\u003e\u003cp\u003eNote that you can\u0027t ask more than \u003cspan class\u003d\"tex-span\"\u003e1999\u003c/span\u003e queries of the type \u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eIf \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d - 1\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e \u003d - 1\u003c/span\u003e, then it means that you asked more queries than allowed, or asked an invalid query. Your program should immediately terminate (for example, by calling \u003cspan class\u003d\"tex-font-style-tt\"\u003eexit(0)\u003c/span\u003e). You will receive \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eWrong Answer\u003c/span\u003e\", 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.\u003c/p\u003e\u003cp\u003eYour solution will get \"Idleness Limit Exceeded\", if you don\u0027t print anything or forget to \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush\u003c/span\u003e the output, including the final answer.\u003c/p\u003e\u003cp\u003eTo \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush\u003c/span\u003e you can use (just after printing a query and line end):\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e in C++; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e in Java; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003estdout.flush()\u003c/span\u003e in Python; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e in Pascal; \u003c/li\u003e\u003cli\u003e For other languages see documentation. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eHacks format\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e\u003cp\u003eFor hacks, use the following format:\u003c/p\u003e\u003cp\u003eIn the first line print three integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estart\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 50000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003estart\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003ex\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eIn the next \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e lines print the description of the elements of the list: in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th line print two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e0 ≤ \u003ci\u003evalue\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e - 1 ≤ \u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≠ 0\u003c/span\u003e).\u003c/p\u003e\u003cp\u003eThe printed structure should be a valid singly linked list. In particular, it should be possible to reach all elements from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003estart\u003c/i\u003e\u003c/span\u003e by following links \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, and the last element \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eend\u003c/i\u003e\u003c/span\u003e should have \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e in the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003enext\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003eend\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 3 80\n97 -1\n58 5\n16 2\n81 1\n79 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e? 1\n? 2\n? 3\n? 4\n? 5\n! 81\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eYou can read more about singly linked list by the following link: \u003ca href\u003d\"https://en.wikipedia.org/wiki/Linked_list#Singly_linked_list\"\u003ehttps://en.wikipedia.org/wiki/Linked_list#Singly_linked_list\u003c/a\u003e \u003c/p\u003e\u003ccenter\u003e\u003cp\u003eThe illustration for the first sample case. Start and finish elements are marked dark. \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/d8a8ef12be490fe14d03d5e7d490a8e6?v\u003d1715873628\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e\u003c/center\u003e"}}]}