P14195 [ICPC 2024 Hangzhou R] Identify Chord

$\textit{This is an interactive problem.}$ Grammy has an undirected cyclic graph of $n$ ($4 \le n \le 10^9$) vertices numbered from $1$ to $n$. An undirected cyclic graph is a graph of $n$ vertices and $n$ undirected edges that form one cycle. Specifically, there is a bidirectional edge between vertex $i$ and vertex $((i\bmod n)+1)$ for each $1 \le i \le n$. Grammy thinks that this graph is too boring, so she secretly chooses a pair of $\textit{non-adjacent}$ vertices and connects an undirected edge (called a chord) between them, so that the graph now contains $n$ vertices and $(n+1)$ edges. Your task is to guess the position of the chord by making no more than $40$ queries. Each query consists of two vertices $x$ and $y$, and Grammy will tell you the number of edges on the shortest path between the two vertices. Note that the interactor is $\textit{non-adaptive}$, meaning that the position of the chord is pre-determined.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^3$) indicating the number of test cases. For each test case: The first line contains an integer $n$ ($4 \le n \le 10^9$) indicating the number of vertices.

To ask a query, output one line. First output \texttt{?} followed by a space, then output two vertices $x$ and $y$ ($1 \le x, y \le n$) separated by a space. After flushing your output, your program should read a single integer indicating the number of edges on the shortest path between the two vertices. To guess the position of the chord, output one line. First output $\texttt{!}$ followed by a space, then output two vertices $u$ and $v$ ($1 \le u, v \le n$) separated by a space, indicating that the chord connects vertices $u$ and $v$. After flushing your output, your program should read a single integer $r$ ($r \in \{1, -1\}$) indicating the correctness of your guess. If $r = 1$ then your guess is correct, and your program should continue processing the next test case, or exit immediately if there are no more test cases. Otherwise if $r = -1$ then your guess is incorrect, and your program should exit immediately to receive a $\texttt{Wrong Answer}$ verdict. Note that your guess does not count as a query. To flush your output, you may use: - $\texttt{fflush(stdout)}$ (if you use $\texttt{printf}$) or $\texttt{cout.flush()}$ (if you use $\texttt{cout}$) in C and C++. - $\texttt{System.out.flush()}$ in Java. - $\texttt{stdout.flush()}$ in Python.

The graphs in the sample test cases are illustrated as follows: :::align{center}  :::