406235: GYM102319 E Enegue's Enigmatic Lanterns

Enegue is enjoying life as he strolls down a mildly overgrown path through the forest. At times, he could catch glimpses of the waning moon through gaps in the canopy. As the he followed the winding path through the undergrowth, Enegue suddenly felt the presence of a being somewhere just beyond his vision. Pausing momentarily, Enegue heard the rustling of leaves somewhere in the distance. Then, $$$n$$$ lanterns appeared in a row in front of Enegue.

"Who," a voice asked.

"Enegue the eyqs," responded Enegue, "who are you?"

The voice simply replied "who." Then, with a bright flash, Enegue saw the silhouette of an owl before all the lanterns went dark. After a brief moment of darkness, $$$k$$$ of the lanterns turned on again, and the owl was nowhere to be seen or heard. Suddenly struck by inspiration, Enegue decides to make you guess which $$$k$$$ of the $$$n$$$ lanterns are shining.

Enegue has a row of $$$n$$$ lanterns, of which $$$k$$$ are on. He wants you to guess which $$$k$$$ of the $$$n$$$ lanterns are on, but he will only answer your questions in a very cryptic fashion. For each question, you are allowed to choose any subset $$$S$$$ of the $$$n$$$ lanterns. Enegue will then count the number of lanterns on in $$$S$$$. Let this number be $$$x$$$, but Enegue will not tell you $$$x$$$. Instead, he will tell you the number of composite divisors of $$$x$$$. (eg. the composite divisors of 12 are $$$\{4,6,12\}$$$, so if $$$x=12$$$, then Enegue will answer with 3).

Since Enegue is a cactus, he will get bored after $$$2\times10^5$$$ questions, so you'll need to guess the $$$k$$$ lanterns that are on before he gets bored.

The initial line of input contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$4\le k\le n\le 100$$$), where $$$n$$$ is the total number of lanterns, and $$$k$$$ is the number of lanterns that are on.

This is an interactive problem. Your program should use standard input and output to communicate with the judge's program.

You are allowed $$$2\times10^5$$$ queries. Each query should contain the character '?' and a string $$$S$$$ of length $$$n$$$, separated by one space. The string $$$S$$$ represents the chosen subset, where the $$$i$$$-th character of $$$S$$$ is a '1' if and only if the $$$i$$$-th lantern is in the subset.

The response to each query will be a single integer as described above. A response of $$$-1$$$ means the query is malformed or you have submitted more than $$$2\times10^5$$$ queries, in which case your program should exit immediately and get a "Wrong Answer".

Once you are ready to guess the $$$k$$$ lanterns, output a single line starting with the character '!' and a string $$$T$$$ of length $$$n$$$, separated by one space. The string $$$T$$$ represents the subset of $$$k$$$ lanterns in the same format as the string $$$S$$$ above. You will get "Accepted" if the guess is correct.

9 5

0

0

// output to show interaction
? 111111111

? 000001111

! 101100101

The sample input and output only show how the interaction works. It will probably get wrong answer.