{"raw_statement":[{"iden":"statement","content":"*This is an interactive problem.*\n\nAs we all know, JXC is the red sun of USST. Now, he is going to play an easy game with Setsuna.\n\nSetsuna is given a grid $n times m$. Rows are enumerated from 1 to $n$ from up to down, and columns are enumerated from $1$ to $m$ from left to right. Cell, standing on the intersection of row $x$ and column $y$, is denoted by $(x, y)$, and the number in cell $(x, y)$ is denoted as $A_{x , y}$.\n\nEvery cell contains $0$ or $1$, but only JXC knows what they are.\n\nSetsuna wants to know numbers in all cells of the grid. To do so we can ask the following questions:\n\nFor example, for the graph below, answer for \"? $1 \" \"1 \" \"3 \" \"3$\" is $4$ and answer for \"$? \" \"3 \" \"4$\" is $0$.\n\nYou are required to help Setsuna to determine all cells of the grid by asking not more than $2000$ questions(including two kinds of questions and the guess of the answer). It can be shown that the answer always exists.\n\nThe first line contains two integers $n, m (3 <= n, m <= 32)$.\n\nYou begin the interaction by reading $n, m$.\n\nTo ask a question about submatrix $(x_1, y_1), (x_2, y_2)$, output \"$? \" \"x_1 \" \"y_1 \" \"x_2 \" \"y_2$\" in a separate line.\n\nNumbers in the query have to satisfy $1 <= x_1 < x_2 <= n$ and $1 <= y_1 < y_2 <= m$.\n\nTo ask a question about the number in cell $(x, y)$, output \"$? \" \"x \" \"y$\" in a separate line.\n\nNumbers in the query have to satisfy $1 <= x <= n$ and $1 <= y <= m$.\n\nDon't forget to 'flush', to get the answer.\n\nIn response, you will receive the number of good pairs if you asked the submatrix or the number in the cell otherwise.\n\nIn case your query was invalid or you asked more than $2000$ queries(including two kinds of questions and the guess of the answer) or you asked more than $5$ queries of the second type, program would print $− 1$ and finish the interaction. You would receive *Wrong answer* verdict. Make sure to exit immediately to avoid getting other verdicts.\n\nWhen you determine numbers in all cells, output \"$!$\". There must be a line break('$backslash$n') after \"$!$\".\n\nThen output $n$ lines, the $i$-th of which is a string of length $m$, corresponding to numbers in the $i$-th row of the grid.\n\nNote that you have only $1$ chance to guess the answer, and after outputting the answer, your program must be terminated immediately without outputting anything.\n\nAfter printing a query, do not forget to output end of line and flush the output. Otherwise, you will get *Idleness limit exceeded*. To do this, use:\n\nThe interaction process in the sample is as follows.\n\nSetsuna first used all the second type of queries to get the numbers in the first five cells. \n\nThen she asked about the $2 times 2$ submatrix in the lower right corner. JXC told her there are $4$ good pairs, so it is easy to infer that this submatrix is all $0$.\n\nFinally she asked about the $2 times 3$ submatrix at the bottom. JXC told her there are $5$ good pairs, so it is easy to infer that the lower left corner is $1$.\n\n"},{"iden":"input","content":"The first line contains two integers $n, m (3 <= n, m <= 32)$."},{"iden":"interaction","content":"You begin the interaction by reading $n, m$.To ask a question about submatrix $(x_1, y_1), (x_2, y_2)$, output \"$? \" \"x_1 \" \"y_1 \" \"x_2 \" \"y_2$\" in a separate line.Numbers in the query have to satisfy $1 <= x_1 < x_2 <= n$ and $1 <= y_1 < y_2 <= m$.To ask a question about the number in cell $(x, y)$, output \"$? \" \"x \" \"y$\" in a separate line.Numbers in the query have to satisfy $1 <= x <= n$ and $1 <= y <= m$.Don't forget to 'flush', to get the answer.In response, you will receive the number of good pairs if you asked the submatrix or the number in the cell otherwise.In case your query was invalid or you asked more than $2000$ queries(including two kinds of questions and the guess of the answer) or you asked more than $5$ queries of the second type, program would print $− 1$ and finish the interaction. You would receive *Wrong answer* verdict. Make sure to exit immediately to avoid getting other verdicts.When you determine numbers in all cells, output \"$!$\". There must be a line break('$backslash$n') after \"$!$\".Then output $n$ lines, the $i$-th of which is a string of length $m$, corresponding to numbers in the $i$-th row of the grid.Note that you have only $1$ chance to guess the answer, and after outputting the answer, your program must be terminated immediately without outputting anything.After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get *Idleness limit exceeded*. To do this, use:  $\"fflush (stdout)\"$ or $\"cout. flush ()\"$ in C++;  $\"System. out. flush ()\"$ in Java;  $\"flush (output)\"$ in Pascal;  $\"stdout. flush ()\"$ in Python;  see documentation for other languages. "},{"iden":"note","content":"The interaction process in the sample is as follows.  Setsuna first used all the second type of queries to get the numbers in the first five cells. Then she asked about the $2 times 2$ submatrix in the lower right corner. JXC told her there are $4$ good pairs, so it is easy to infer that this submatrix is all $0$.Finally she asked about the $2 times 3$ submatrix at the bottom. JXC told her there are $5$ good pairs, so it is easy to infer that the lower left corner is $1$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ S \\subseteq \\mathbb{Z}_{\\geq 0} $ be the set of numbers stored in the machine.  \nLet $ \\mathcal{P}(S) $ denote the power set of $ S $.  \nThe set of token numbers is $ T = \\left\\{ \\bigoplus_{x \\in A} x \\,\\middle|\\, A \\in \\mathcal{P}(S) \\right\\} $, where $ \\oplus $ denotes XOR, and $ \\bigoplus_{x \\in \\emptyset} x = 0 $.  \n\n**Constraints**  \n1. $ 1 \\le q \\le 10^6 $  \n2. For each query:  \n   - If $ p = 1 $: $ 1 \\le n \\le 10^9 $, update $ S \\leftarrow S \\cup \\{n\\} $  \n   - If $ p = 2 $: $ 1 \\le n \\le |T| $, query the $ n $-th smallest element of $ T $  \n\n**Objective**  \nAfter processing each query:  \n- For $ p = 1 $: Update $ S $.  \n- For $ p = 2 $: Output the $ n $-th smallest element of $ T $, where $ T $ is the set of all XORs of subsets of $ S $.","simple_statement":"You are given a machine that stores numbers. For each query:\n\n- If type 1: Add a number to the machine.\n- If type 2: Find the n-th smallest XOR value you can get from any subset of stored numbers (including empty subset → 0).\n\nOutput the token number for each type-2 query.","has_page_source":false}