Mahmoud and Ehab and the binary string
Contest: Codeforces Round 435 (Div. 2)
Difficulty rating: 2000
Tags: binary search, divide and conquer, interactive

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.

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 .

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

Output format:
To print the final answer, print "! pos0 pos1" (without quotes), where pos0 and pos1 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!

Interaction format:
To ask a question use the format "? s" (without quotes), where s is a query string. Don't forget to flush the output after printing a query!

After each query you can read a single integer from standard input — the Hamming distance between the hidden string and the query string.

To flush the output you can use:-

- fflush(stdout) in C++;
- System.out.flush() in Java;
- stdout.flush() in Python;
- flush(output) in Pascal;
- See the documentation for other languages .

Hacking.

To hack someone just print one binary string with length up to 1000, containing at least one '0' and at least one '1'.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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".

Example input:
3
2
1
3
2
1
0

Example output:
? 000
? 001
? 010
? 011
? 100
? 101
! 2 1

Editorial:
**In the editorial we suppose that the answer of some query is the number of correct guessed positions which is equal to n minus hamming distance, The solutions in this editorial consider the answer of a query as n minus real answer, For convenience.**
**Common things** : Let zero(l, r) be a function that returns the number of zeros in the interval [l;r] minus the number of ones in it, We can find it in one query after a preprocessing query, The preprocessing query is 1111..., Let its answer be stores in all, If we made a query with a string full of ones except for the interval [l;r] which will be full of zeros, If this query's answer is cur, zero(l, r) = cur - all, That's because all is the number of ones in the interval [l;r] plus some trash and cur is the number of zeros in the interval plus the same trash.
#### First solution by [user:mahmoudbadawy,2017-09-17]
Let's have a searching interval, initially this interval is [1;n] (The whole string), Let's repeat this until we reach our goal, Let mid = (l + r) / 2 Let's query to get zero(l, mid), If it's equal to r - l + 1, This interval is full of zeros so we can print any index in it as the index with value 0 and continue searching for an index with the value 1 in the interval [mid + 1;r], But if its value is equal to l - r - 1, This interval is full of ones so we can print any index in it as the index with value 1 and continue searching for a 0 in the interval [mid + 1;r], Otherwise the interval contains both values so we can continue searching for both in the interval [l;mid], Every time the searching interval length must be divided by 2 in any case so we perform O(log(n)) queries.
#### Second solution by me
Let's send 1111... and let the answer be ans1, Let's send 0111... and let the answer be ans0, We now know the value in the first index (1 if ans1 > ans0, 0 otherwise), We can binary search for the first index where the non-found value exists, which is to binary search on the first value x where zero(2, x) * sign(non - found bit value) ≠ x - 1 where sign(y) is 1 if y = 0,  - 1 otherwise.
Solution link (me) : TODO.
Solution link ([user:mahmoudbadawy,2017-09-17]) : TODO.
Your thoughts are welcome in the comments.