{"raw_statement":[{"iden":"problem statement","content":"**This is an interactive task** (where your program interacts with the judge's program via input and output).\nWe have an $N$\\-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$\\-th row from the top and $j$\\-th column from the left is denoted by $(i, j)$.  \nConsider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.\n\n*   No row contains two or more rooks.\n*   No column contains two or more rooks.\n\nNow, $N-1$ rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)\nHowever, you cannot directly see which squares of the chessboard are occupied by a rook.  \nInstead, you may ask at most $20$ questions to the judge in the following manner.\n\n*   You choose integers $A$, $B$, $C$, and $D$ such that $1 \\leq A \\leq B \\leq N, 1 \\leq C \\leq D \\leq N$, and ask the number of rooks in the rectangular region formed by the squares $(i, j)$ such that $A \\leq i \\leq B, C \\leq j \\leq D$.\n\nFind a square to place a rook."},{"iden":"constraints","content":"*   $2 \\leq N \\leq 10^3$\n*   $N$ is an integer."},{"iden":"input and output","content":"This is an interactive task (where your program interacts with the judge's program via input and output).\nFirst, receive the size of the chessboard, $N$, from Standard Input.\n\n$N$\n\nNext, repeat asking a question until you find a square to place a rook.  \nA question should be printed to Standard Output in the following format:\n\n$?$ $A$ $B$ $C$ $D$\n\nThe response will be given from Standard Input in the following format:\n\n$T$\n\nHere, $T$ is the response to the question, or `-1` if the question is invalid or more than $20$ questions have been asked.\nWhen the judge returns `-1`, the submission is already regarded as incorrect. In this case, terminate the program immediately.\nWhen you find a square to place a rook, let $(X, Y)$ be that square and print an answer in the following format. Then, terminate the program immediately.\n\n$!$ $X$ $Y$\n\nIf there are multiple appropriate answers, any of them will be accepted."},{"iden":"notes","content":"*   **Each time you print something, end it with a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.**\n*   **If an invalid output is printed during the interaction, the verdict will be indeterminate.**\n*   Terminate the program immediately after printing an answer. Otherwise, the verdict will be indeterminate."},{"iden":"sample interaction","content":"Below is an interaction where $N=3$ and the rooks are placed on $(1, 2)$ and $(2, 1)$.\n\nInput\n\nOutput\n\nDescription\n\n`3`\n\nJudge first gives the integer $N$.\n\n`? 1 2 1 3`\n\nParticipant asks a question with $(A,B,C,D)=(1,2,1,3)$.\n\n`2`\n\nJudge returns the answer to the question, which is $2$.\n\n`? 2 3 1 1`\n\nParticipant asks a question with $(A,B,C,D)=(2,3,1,1)$.\n\n`1`\n\nJudge returns the answer to the question, which is $1$.\n\n`? 1 3 3 3`\n\nParticipant asks a question with $(A,B,C,D)=(1,3,3,3)$.\n\n`0`\n\nJudge returns the answer to the question, which is $0$.\n\n`! 3 3`\n\nParticipant finds the answer to be $(3, 3)$ and prints it."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}