CF862D.Mahmoud and Ehab and the binary string

Mahmoud and Ehab are in the fourth stage now.

Dr. Evil has a hidden binary string of length n. He guarantees that there is at least one '0' symbol and at least one '1' symbol in it. Now he wants Mahmoud and Ehab to find a position of any '0' symbol and any '1' symbol. In order to do this, Mahmoud and Ehab can ask Dr. Evil up to 15 questions. They tell Dr. Evil some binary string of length n, 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.

Help Mahmoud and Ehab find these two positions.

You will get Wrong Answer verdict if

• Your queries doesn't satisfy interaction protocol described below.
• You ask strictly more than 15 questions and your program terminated after exceeding queries limit. Please note, that you can do up to 15 ask queries and one answer query.
• Your final answer is not correct.

You will get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output, including for the final answer (more info about flushing output below).

If you exceed the maximum number of queries, You should terminate with 0, In this case you'll get Wrong Answer, If you don't terminate you may receive any verdict because you'll be reading from a closed stream .

马哈茂德和埃哈布现在进入了第四关。

邪恶博士手中有一个长度为 $n$ 的隐藏二进制字符串。他保证该字符串中至少包含一个 '0' 字符，也至少包含一个 '1' 字符。现在，他要求马哈茂德和埃哈布找出任意一个 '0' 字符的位置以及任意一个 '1' 字符的位置。为此，他们最多可以向邪恶博士提出 15 个问题。每次提问时，他们向邪恶博士提交一个长度为 $n$ 的二进制字符串；邪恶博士则会返回该字符串与隐藏字符串之间的汉明距离（Hamming distance）。两个等长二进制字符串之间的汉明距离，是指它们在相同位置上字符不同的位置个数。汉明距离的定义详见下方“注意事项”部分。

请帮助马哈茂德和埃哈布找出这两个位置。

若出现以下任一情况，你将得到 Wrong Answer（错误答案） 判定：

• 你的查询不符合下文所述的交互协议；
• 你提出的查询次数严格超过 15 次，且你的程序在超出查询次数限制后终止。请注意：你最多可进行 15 次询问查询（ask query） 和 1 次回答查询（answer query）；
• 你给出的最终答案不正确。

若你未输出任何内容，或忘记刷新输出（包括最终答案的输出），你将得到 Idleness Limit Exceeded（空闲超时） 判定（有关刷新输出的更多信息见下文）。

如果你超出了最大查询次数，你应当以退出码 0 主动终止程序；此时你将得到 Wrong Answer。如果你未主动终止，由于后续将从已关闭的输入流中读取数据，你可能会收到任意类型的判定。

The first line of input will contain a single integer n (2 ≤ n ≤ 1000) — the length of the hidden binary string.

输入的第一行包含一个整数 $n$（$2 \leq n \leq 1000$）—— 表示隐藏的二进制字符串的长度。

To print the final answer, print "! pos0 pos1" (without quotes), where _pos_0 and _pos_1 are positions of some '0' and some '1' in the string (the string is 1-indexed). Don't forget to flush the output after printing the answer!

要输出最终答案，请输出 ! pos0 pos1（不带引号），其中 pos0 和 pos1 分别是字符串中某个 '0' 和某个 '1' 的位置（字符串下标从 1 开始）。输出答案后务必刷新输出！

Hamming distance definition: https://en.wikipedia.org/wiki/Hamming_distance

In the first test case the hidden binary string is 101, The first query is 000, so the Hamming distance is 2. In the second query the hidden string is still 101 and query is 001, so the Hamming distance is 1.

After some queries you find that symbol at position 2 is '0' and symbol at position 1 is '1', so you print "! 2 1".

汉明距离定义：https://en.wikipedia.org/wiki/Hamming_distance

在第一个测试用例中，隐藏的二进制字符串为 101。第一次查询为 000，因此汉明距离为 2。第二次查询中，隐藏字符串仍为 101，而查询字符串为 001，因此汉明距离为 1。

经过若干次查询后，你发现位置 2 上的字符是 '0'，位置 1 上的字符是 '1'，于是你输出 "! 2 1"。