Limits 2s, 512 MB · Interactive

This is an Interactive Problem.

The judge has a secret binary string SS of length n(1n1000)n(1 \leq n \leq 1000).

You can do several queries on the string.

To do a query, print “? QQ”. Here QQ is any binary string of length m(1m2×n)m(1 \leq m \leq 2 \times n).

The judge replies to your query with an integer, the number of substrings of SS that are lexicographically smaller than QQ.

Find the secret string by asking no more than 2×n2 \times n queries.

When you have figured out the secret string, print “! SS” in a line and move on to the next test case.


The first line contains a single integer T(1T100)T(1 \leq T \leq 100) — the number of test cases.

Each test case starts with reading the integer nn, the length of the secret string in that test case. The sum of nn in all the test cases does not exceed 20002000.

Interaction Details

For each query, print the query in a line and flush the output. The query should be in the format mentioned above.

After each query, read an integer: the response from the judge. 1-1 as a response from the judge means you did an invalid query. If you do any invalid query, your submission will fail with an arbitrary incorrect verdict.

After confirming the secret string in a test case, move on to the next test case if there is any, terminate your program otherwise.

To flush the output stream, you may use:

  • fflush(stdout) in C/C++

  • stdout.flush() in Python


A sample interaction is given below for a test with two test cases, the first string is “001” and the second string is “11”.

>> 2
>> 3
<< ? 0
>> 0
<< ? 1
>> 5
<< ! 001
>> 2
<< ? 0
>> 0
<< ? 1
>> 0
<< ! 11

Another sample with a single test case and the secret string being “01”.

>> 1
>> 2
<< ? 0101
>> 2
<< ? 101011
>> -1

Here >> indicates what your program reads and << indicates what your program writes. These symbols are here to make it easy to understand. You do not have to print such symbols from your program.


  • Binary strings are strings consisting of characters 0 and/or 1.

  • Substrings of a string are collections of one or more consecutive characters of that string in the same order they appear in the original string.

  • String A is said to be lexicographically smaller than string B if either string A is a prefix of string B or the first index where characters in the strings mismatch, character in string A has a lower ASCII value.


Login to submit.


0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.