G. Guess the Polygon
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

This is an interactive problem.

You are given a simple polygon, but before giving you the $$$n$$$ vertices of the polygon, Little Q has shuffled them.

Now you can ask Little Q no more than $$$(n-2)$$$ queries, each of which consists of two integers $$$p$$$ and $$$q$$$ ($$$0 \le p/q \le 1\,000, 1 \le q \le 1\,000$$$). He will tell you the total length of the points on the line $$$x=p/q$$$ that lie inside or on the boundary of the polygon, which can be represented as $$$r/s$$$ with two integers $$$r$$$ and $$$s$$$ ($$$r \ge 0, s \ge 1, \gcd(r,s) = 1$$$). Here $$$\gcd(r,s)$$$ is the greatest common divisor of $$$r$$$ and $$$s$$$.

You need to find the area of the polygon, which can also be represented as $$$u/v$$$ with two integers $$$u$$$ and $$$v$$$ ($$$u \ge 0, v \ge 1, \gcd(u,v) = 1$$$).

The polygon and the order of the vertices are determined before the start of the interaction and do not depend on your queries. In other words, the interactor is not adaptive.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 1\,000$$$), indicating the number of test cases. For each test case:

The first line contains an integer $$$n$$$ ($$$3 \le n \le 1\,000$$$), indicating the number of vertices of the polygon.

Then $$$n$$$ lines follow, each containing two integers $$$x$$$ and $$$y$$$ ($$$0 \le x,y \le 1\,000$$$) that give the coordinates $$$(x, y)$$$ of the vertices of the polygon in shuffled order.

The polygon is simple, i.e., its vertices are distinct and no two edges of the polygon intersect or touch, except that consecutive edges touch at their common vertex. In addition, no two consecutive edges are collinear.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1\,000$$$.

Interaction

If you want to ask a query, output one line. First output ? followed by a space, then output two integers $$$p$$$ and $$$q$$$ ($$$0 \le p/q \le 1\,000, 1 \le q \le 1\,000$$$). After flushing your output, your program should read two integers $$$r$$$ and $$$s$$$ ($$$r \ge 0, s \ge 1, \gcd(r,s) = 1$$$), indicating the answer to your query.

If you want to guess the area of the polygon, output one line. First output ! followed by a space, then output two integers $$$u$$$ and $$$v$$$ ($$$u \ge 0, v \ge 1, \gcd(u,v) = 1$$$), indicating that the area of the polygon is $$$u/v$$$. After flushing your output, your program should continue processing the next test case, or exit immediately if there are no more test cases. Note that your guess does not count as a query.

To flush your output, you can use:

  • fflush(stdout) (if you use printf) or cout.flush() (if you use cout) in C and C++.
  • System.out.flush() in Java and Kotlin.
  • sys.stdout.flush() in Python.
Example
Input
2
4
0 0
1 3
1 1
3 0

2 1

3
0 0
999 1000
1000 999

1999 999000
Output






? 1 1

! 3 1




? 1 1

! 1999 2
Note

For the first sample case, there are three candidate polygons, shown in the figure below. Only the leftmost one meets the answer $$$2$$$ to the query $$$x=1$$$, and thus the area is $$$3$$$. The other two have the answer $$$3$$$ to the query $$$x=1$$$.

For the second sample case, there is only one candidate polygon, and thus the area is $$$1999/2$$$.

Note that the order of the vertices shown in the sample case may not be consistent with the actual provided.

The blank lines in the sample case are added for readability. In your output, extra spaces or blank lines will be ignored.