Some of you may wondered what kind of query you should ask, because the chess board is in a two-dimensional plane.
For simplicity, let us first consider a one-dimensional case. That is, consider the following problem:

We have a sequence \((A_1, A_2, \dots, A_N)\). \(N-1\) of the \(N\) elements in \(A\) are \(1\), and the other one is \(0\). Repeat the following question to determine \(i\) such that \(A_i = 0\).

• Choose \(P\) and \(Q\). Ask how many \(1\)’s are there in \(A_P, A_{P+1}, \dots, A_{Q}\).

This problem can be solved with binary search through at most \(\lceil \log_2 N \rceil\) questions.
Specifically, perform the following steps:

• First, let \(L = 1, R = N\). \(L\) and \(R\) means that the answer is contained in \(\lbrack L, R \rbrack\).
• While \(L \neq R\), make the following query:
  • Let \(M = \lfloor (L + R) / 2 \rfloor\), and ask a query with \((P, Q) = (L, M)\). The possible response to the query is either \(M-L+1\) or \(M-L\); we perform differently depending on this value:

     - If the answer to the query is $M-L$, it means that $\lbrack L, M \rbrack$ contains $0$, so let $R \gets M$.
     - If the answer to the query is $M-L+1$, it maens that $\lbrack L, M \rbrack$ does not contain $0$, so let $L \gets M + 1$.
    

Since the inspected segment is halved in each iteration, we can find the answer through \(\lceil \log_2 N \rceil\) questions.

In fact, the algorithm can be adopted to two-dimensional cases.
Let us divide the problem. Since there are only one possible square, we can solve the problem if we know the following two:

• Which column does not contain a rook?
• Which row does not contain a rook?

Consider finding these answers separately.
First, let us fix \((C, D)\) to \((1, N)\). Then the query is against the region from \(1\)-st through \(N\)-th column, that is, the entire row for each fixed row. Then the contribution to the answer of each column is \(1\) if it has a rook, or \(0\) otherwise. Thus, it is boiled down to the same situation for the one-dimensional case. That is, we can apply the algorithm above, regarding \(A\) and \(B\) as \(L\) and \(R\), so that we can determine “which row does not contain a rook” through \(\lceil \log_2 N \rceil\) questions. Similarly, we can fix \((A, B)\) to \((1, N)\) to find “which column does not contain a rook?”
With these two pieces of information, we can find which square to place a rook. The maximum number of questions required is \(\lceil \log_2 N \rceil \times 2 \leq 10 \times 2 = 20\) times, which exactly fits in the limit of the number of queries. Also, the complexity is \(\mathrm{O}(\log N)\), which is fast enough. Therefore, the problem has been solved.

The following is a sample code in C++. Here are some tips:

• In C++, by appending endl to the output, it is flushed right after creating a new line. (When writing an interactive code in C++, all you have to care is this endl.) However, if you replace endl with "\n" with a macro, it may not be flushed, so be careful if you are using your original macros.
  • However, strictly speaking, the sample code still works and gets AC (accepted) even if endl is replaced with "\n". If you are curious, go ahead and check the specifications of C++.
• As in the send function in the 4-th line, it is useful to define a function that receives the output to the judge program as arguments and the values passed from the judge as the return values, in order to reduce cin, cout, etc. and clarify the implementation.
• As in the sample code, it may be useful to manage the segment of the binary search as a half-open segment \([1, N+1)\) to reduce the conditional branches and help implementation easier. (It may depend on preference.)

#include <iostream>
using namespace std;

int send(int A, int B, int C, int D) {
  cout << "? " << A << " " << B << " " << C << " " << D << endl;
  cin >> A;
  return A;
}

int main() {
  int N;
  cin >> N;
  int U = 1, D = N + 1;
  while (U + 1 != D) {
    int M = (U + D) / 2;
    int c = send(U, M - 1, 1, N);
    (c == M - U ? U : D) = M;
  }
  int L = 1, R = N + 1;
  while (L + 1 != R) {
    int M = (L + R) / 2;
    int c = send(1, N, L, M - 1);
    (c == M - L ? L : R) = M;
  }
  cout << "! " << U << " " << L << endl;
}