{"trustable":false,"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":"\u003cdiv\u003e\n \u003cp\u003eMahmoud and Ehab are in the fourth stage now.\u003c/p\u003e\n \u003cp\u003eDr. Evil has a hidden binary string of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. He guarantees that there is at least one \u00270\u0027 symbol and at least one \u00271\u0027 symbol in it. Now he wants Mahmoud and Ehab to find a position of any \u00270\u0027 symbol and any \u00271\u0027 symbol. In order to do this, Mahmoud and Ehab can ask Dr. Evil up to \u003cspan class\u003d\"tex-span\"\u003e15\u003c/span\u003e questions. They tell Dr. Evil some binary string of length \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e, and Dr. Evil tells the Hamming distance between these two strings. Hamming distance between 2 binary strings of the same length is the number of positions in which they have different symbols. You can find the definition of Hamming distance in the notes section below.\u003c/p\u003e\n \u003cp\u003eHelp Mahmoud and Ehab find these two positions.\u003c/p\u003e\n \u003cp\u003eYou will get \u003cspan class\u003d\"tex-font-style-it\"\u003eWrong Answer\u003c/span\u003e verdict if \u003c/p\u003e\n \u003cul\u003e \n \u003cli\u003e Your queries doesn\u0027t satisfy interaction protocol described below. \u003c/li\u003e\n \u003cli\u003e You ask strictly more than \u003cspan class\u003d\"tex-span\"\u003e15\u003c/span\u003e questions and your program terminated after exceeding queries limit. Please note, that you can do up to \u003cspan class\u003d\"tex-span\"\u003e15\u003c/span\u003e ask queries and one answer query. \u003c/li\u003e\n \u003cli\u003e Your final answer is not correct. \u003c/li\u003e\n \u003c/ul\u003e You will get \n \u003cspan class\u003d\"tex-font-style-it\"\u003eIdleness Limit Exceeded\u003c/span\u003e if you don\u0027t print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).\n \u003cp\u003eIf you exceed the maximum number of queries, You should terminate with 0, In this case you\u0027ll get Wrong Answer, If you don\u0027t terminate you may receive any verdict because you\u0027ll be reading from a closed stream .\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"input-specification\"\u003e\n \u003cdiv class\u003d\"section-title\"/div\u003e\n \u003cp\u003eThe first line of input will contain a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1000\u003c/span\u003e)\u0026nbsp;— the length of the hidden binary string.\u003c/p\u003e\n\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"output-specification\"\u003e\n \u003cdiv class\u003d\"section-title\"/div\u003e\n \u003cp\u003eTo print the final answer, print \"! pos0 pos1\" (without quotes), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epos\u003c/i\u003e0\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003epos\u003c/i\u003e1\u003c/span\u003e are positions of some \u00270\u0027 and some \u00271\u0027 in the string (the string is 1-indexed). \u003cspan class\u003d\"tex-font-style-bf\"\u003eDon\u0027t forget to flush the output after printing the answer!\u003c/span\u003e\u003c/p\u003e\n\u003c/div\u003e\n\n"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cdiv\u003e\u003cp\u003eTo ask a question use the format \"? s\" (without quotes), where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003es\u003c/i\u003e\u003c/span\u003e is a query string. \u003cspan class\u003d\"tex-font-style-bf\"\u003eDon\u0027t forget to flush the output after printing a query!\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAfter each query you can read a single integer from standard input\u0026nbsp;— the Hamming distance between the hidden string and the query string.\u003c/p\u003e\u003cp\u003eTo flush the output you can use:- \u003c/p\u003e\u003cul\u003e \u003cli\u003e fflush(stdout) in C++; \u003c/li\u003e\u003cli\u003e System.out.flush() in Java; \u003c/li\u003e\u003cli\u003e stdout.flush() in Python; \u003c/li\u003e\u003cli\u003e flush(output) in Pascal; \u003c/li\u003e\u003cli\u003e See the documentation for other languages . \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eHacking.\u003c/span\u003e \u003c/p\u003e\u003cp\u003eTo hack someone just print one binary string with length up to \u003cspan class\u003d\"tex-span\"\u003e1000\u003c/span\u003e, containing at least one \u00270\u0027 and at least one \u00271\u0027.\u003c/p\u003e\u003c/div\u003e"}},{"title":"Example","value":{"format":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e\u003cdiv class\u003d\"sample-tests\"\u003e\n \u003cdiv class\u003d\"section-title\"/div\u003e\n \u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e3\u003cbr\u003e2\u003cbr\u003e1\u003cbr\u003e3\u003cbr\u003e2\u003cbr\u003e1\u003cbr\u003e0\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e? 000\u003cbr\u003e? 001\u003cbr\u003e? 010\u003cbr\u003e? 011\u003cbr\u003e? 100\u003cbr\u003e? 101\u003cbr\u003e! 2 1\u003c/pre\u003e\n \u003c/div\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cdiv class\u003d\"note\"\u003e\n \u003cdiv class\u003d\"section-title\"Note/div\u003e\n \u003cp\u003eHamming distance definition: \u003ca href\u003d\"https://en.wikipedia.org/wiki/Hamming_distance\"\u003ehttps://en.wikipedia.org/wiki/Hamming_distance\u003c/a\u003e\u003c/p\u003e\n \u003cp\u003eIn the first test case the hidden binary string is 1\u003cspan class\u003d\"tex-font-style-bf\"\u003e0\u003c/span\u003e1, The first query is 0\u003cspan class\u003d\"tex-font-style-bf\"\u003e0\u003c/span\u003e0, so the Hamming distance is \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e. In the second query the hidden string is still 1\u003cspan class\u003d\"tex-font-style-bf\"\u003e01\u003c/span\u003e and query is 0\u003cspan class\u003d\"tex-font-style-bf\"\u003e01\u003c/span\u003e, so the Hamming distance is \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e.\u003c/p\u003e\n \u003cp\u003eAfter some queries you find that symbol at position \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e is \u00270\u0027 and symbol at position \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e is \u00271\u0027, so you print \"! 2 1\".\u003c/p\u003e\n\u003c/div\u003e"}}]}