{"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\u003eThe world famous scientist Innokentiy created \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e nuclear circuits. But some of them appeared to be defective, and he forgot which exactly. Luckily, only strictly less than a half of circuits were defective, and now the scientist wants to find out which circuits are operational and which are not.\u003c/p\u003e\u003cp\u003eThe scientist can connect two circuits with each other, and each of them will tell whether the other one is operational or not. An operational circuit always gives the right answer, while a defective one can give any answer. Defective circuits can give different answers for the same checks. You should help the scientist to determine which circuits are operational, and do it quickly, because the circuits are, well, nuclear, and if the scientist will not finish in \u003cspan class\u003d\"tex-span\"\u003e4\u003ci\u003en\u003c/i\u003e\u003c/span\u003e checks, a radiation will cause him irretrievable damage.\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eThis is an interactive problem. Your program should communicate with the jury\u0027s program, using standard input and output for that.\u003c/p\u003e\u003cp\u003eAt the very beginning, you program gets a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 5000\u003c/span\u003e)\u0026nbsp;— the number of circuits.\u003c/p\u003e\u003cp\u003eAfter that you can make at most \u003cspan class\u003d\"tex-span\"\u003e4\u003ci\u003en\u003c/i\u003e\u003c/span\u003e checks. To do that, output character «\u003cspan class\u003d\"tex-font-style-tt\"\u003e?\u003c/span\u003e» and two distinct integers\u0026nbsp;— the numbers of circuits \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e you want to connect and check. Circuits are numbered from one.\u003c/p\u003e\u003cp\u003eAs a response you will get two characters, each of which is «\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e» or «\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e». The first character is the output of circuit \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e about condition of circuit \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e, and the second character is the output of circuit \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e about condition of circuit \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e. The character «\u003cspan class\u003d\"tex-font-style-tt\"\u003e+\u003c/span\u003e» means a circuit is operational, and «\u003cspan class\u003d\"tex-font-style-tt\"\u003e-\u003c/span\u003e» means it is defective.\u003c/p\u003e\u003cp\u003eAs soon as you determine conditions of all circuits, output character «\u003cspan class\u003d\"tex-font-style-tt\"\u003e!\u003c/span\u003e», then the integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e\u0026nbsp;— the number of operational circuits, and then \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003c/span\u003e distinct integers\u0026nbsp;— their numbers. After that your program must terminate.\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\n\n+ +\n\n- +\n\n+ +\n\n- +\n\n- +\n\n+ +\n\n- +\n\n- -\n\n- +\n\n- -\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e? 1 2\n\n? 1 3\n\n? 1 4\n\n? 1 5\n\n? 2 3\n\n? 2 4\n\n? 2 5\n\n? 3 4\n\n? 3 5\n\n? 4 5\n\n! 3 1 2 4\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\u003ePlease note that each your message must end with a line break. Also after outputting each message your program must flush the stream buffer, so that the outputted information could reach jury\u0027s program: for instance, this can be done by calling «\u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e» or «\u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e» in C++, «\u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e» in Java, «\u003cspan class\u003d\"tex-font-style-tt\"\u003eConsole.Out.Flush()\u003c/span\u003e» in C#, «\u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e» in Pascal, «\u003cspan class\u003d\"tex-font-style-tt\"\u003esys.stdout.flush()\u003c/span\u003e» in Python.\u003c/p\u003e"}}]}