Convex

题目描述

This is an interactive problem.

There is a hidden strictly convex polygon $P$. The polygon $P$ has exactly $n$ vertices. All vertices are integer points, and each vertex $(x,y)$ satisfies $|x| \le 10^6$ and $|y| \le 10^6$.

You may ask the interactor an integer vector $(a,b)$. The interactor will return the integer value $\max_{p \in P} (a p_x + b p_y)$, where $p=(p_x,p_y)$ is any point inside or on the boundary of polygon $P$.

Your task is to determine all vertices of polygon $P$ using no more than $3n$ queries.

输入格式

First, read an integer $T$ ($1 \le T \le 100$), denoting the number of test cases.

For each test case, first read an integer $n$ ($3 \le n \le 500$), denoting the number of vertices of the hidden polygon.

It is guaranteed that the sum of $n$ over all test cases does not exceed $500$.

Also, it is guaranteed that the interactor is non-adaptive, which means the polygon is determined before interaction.

输出格式

To ask a query with vector $(a,b)$ ($-10^9 \le a \le 10^9$, $-10^9 \le b \le 10^9$, and $(a,b) \ne (0,0)$), output:

$? \space a \space b$

Then you should read an integer $s$, where $s=\max_{p \in P} (a p_x + b p_y)$.

When you have determined all vertices of polygon $P$ for the current test case, output:

$! \space x_1 \space y_1\space x_2 \space y_2 \dots x_n \space y_n$

Here, $(x_i,y_i)$ ($|x_i| \le 10^6$, $|y_i| \le 10^6$) are all vertices of polygon $P$. You may output the vertices in any order.

After outputting the answer, you should continue to the next test case.

样例输入 #1

1
3

19

20

0

30

20

样例输出 #1

? 4 5

? -1 7

? -2 -9

? 0 10

? 5 -1

! 0 0 4 0 1 3