{"raw_statement":[{"iden":"problem statement","content":"This is an **interactive problem**, where your program interacts with the judge system via Standard Input and Output.\nYou are given integers $N$, $K$, and $Q$.  \nThe judge holds a hidden permutation $(a_1, a_2, \\dots, a_N)$ of $(1, 2, \\dots, N)$.  \nYou may ask up to $Q$ queries to the judge, where each query is as follows:\n\n*   Choose a subset $S$ from $\\lbrace 1, 2, \\dots, N \\rbrace$. The judge will return the number of distinct pairs $(i, j)$ such that $i < j$ and $|a_i - a_j| \\leq K$ where $i, j \\in S$.\n\nLet $x$ be the index $t$ where $a_t = 1$, and $y$ be the index $t$ where $a_t = N$. Your task is to identify the set $\\lbrace x, y \\rbrace$. (You do not need to distinguish which is $x$ and which is $y$.)\nThe judge is non-adaptive, that means the permutation $(a_1, a_2, \\dots, a_N)$ is fixed before any interaction begins."},{"iden":"constraints","content":"*   All input values are integers.\n*   $N = 20000$\n*   $1 \\leq K \\leq 10$\n*   $Q = 30(K + 1)$"},{"iden":"partial score","content":"$30$ points will be awarded for passing the test set satisfying the additional constraint $K = 10$."},{"iden":"input and output","content":"This is an interactive problem.\nFirst, read integers $N$, $K$, and $Q$ from the Standard Input:\n\n$N$ $K$ $Q$\n\nThen, repeat the following process until you identify the set $\\lbrace x, y \\rbrace$:\nFor a query, output the following format to the Standard Output:\n\n? $s_1s_2 \\dots s_N$\n\nHere, $s_1 s_2 \\dots s_N$ is a binary string of length $N$ representing the subset $S$, where $s_i = {}$`1` if $i \\in S$, and $s_i = {}$`0` otherwise.\nThe response to your query will be provided in the Standard Input in the following format:\n\n$T$\n\nHere, $T$ is the answer to the query, representing the number of distinct pairs $(i, j)$ such that $i < j$ and $|a_i - a_j| \\leq K$ where $i, j \\in S$.\nOnce you identify the set $\\lbrace x, y \\rbrace$, output the two elements in the following format (order does not matter) and terminate your program immediately:\n\n! $x$ $y$\n\n### Notes\n\n*   **Print a newline and flush Standard Output at the end of each message. Otherwise, you may get a TLE verdict.**\n*   If your query format is invalid or you exceed the number of queries, the judge will respond with $T = -1$. If you receive this response, you should immediately terminate your program. Otherwise, you may get a TLE verdict.\n*   Beware that unnecessary newlines are considered as malformed."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}