310392: CF1826F. Fading into Fog

F. Fading into Fogtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

This is an interactive problem.

There are $n$ distinct hidden points with real coordinates on a two-dimensional Euclidean plane. In one query, you can ask some line $ax + by + c = 0$ and get the projections of all $n$ points to this line in some order. The given projections are not exact, please read the interaction section for more clarity.

Using the minimum number of queries, guess all $n$ points and output them in some order. Here minimality means the minimum number of queries required to solve any possible test case with $n$ points.

The hidden points are fixed in advance and do not change throughout the interaction. In other words, the interactor is not adaptive.

A projection of point $A$ to line $ax + by + c = 0$ is the point on the line closest to $A$.

Input

The first line contains a single integer $t$ ($1 \leq t \leq 50$) — the number of test cases.

The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 25$) — the number of hidden points.

For each test case, it is guaranteed that for any pair of hidden points, their $x$ coordinates differ by at least $1$. Analogously, $y$ coordinates of any pair also differ by at least $1$.

Coordinates $x$ and $y$ of all hidden points do not exceed $100$ by absolute value.

Interaction

To query a line $ax + by + c = 0$ you should print "? a b c" where all a, b and c are real numbers up to $100$ by absolute value. For less precision issues numbers $a$ and $b$ must satisfy the condition $|a| + |b| \geq 0.1$, where $|a|$ is the absolute value of $a$.

As an answer to the query you will get $n$ points in the form "x_1 y_1 ... x_n y_n", where points $(x_i, y_i)$ are projections to the line $ax + by + c = 0$. It is guaranteed that each printed point is no more than $10^{-4}$ away from the real projection point. Every coordinate is printed with at most 9 decimal places.

See the interaction example for more clarity.

If you ask too many queries, you will get Wrong answer.

To output an answer you should print "! x_1 y_1 ... x_n y_n", where $(x_i, y_i)$ are coordinates of the hidden points. You could output the hidden points in any order. The answer would be considered correct if each of the printed points is no more than $10^{-3}$ away from the corresponding hidden point. Printing the answer doesn't count as a query.

After printing a query or the answer, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see the documentation for other languages

Hacks

To make a hack, use the following test format.

In the first line output a single integer $t$ ($1 \leq t \leq 50$) — the number of test cases.

The description of the test cases follows.

In the first line of each test case output a single integer $n$ ($2 \leq n \leq 25$). In the next $n$ lines output two rational numbers each. The numbers in line $i$ should correspond to $x_i$ and $y_i$ respectively. Printed points must comply with all constraints from the input section.

ExampleInput

1
2

1 1 2.5 1

1.500000001 1.500000000 2 2

Output

? 0 1 -1

? 0.2 -0.2 0

! 1 3 2.5 0.500000001

Note

In the sample the hidden points are $(1, 3)$ and $(2.5, 0.5)$

A picture, which describes the first query:

A picture, which describes the second query:

题目大意：这是一个交互式问题。在二维欧几里得平面上有n个具有实坐标的不同隐藏点。你可以通过一次查询询问一条直线ax + by + c = 0，并获得所有n个点对此直线的投影，以某种顺序给出。提供的投影并非精确值，请阅读交互部分以获得更清晰的信息。

使用最少的查询次数，猜测所有n个点并以某种顺序输出它们。这里的“最少”意味着解决任意具有n个点的测试案例所需的最小查询次数。

隐藏点事先固定，不会在交互过程中改变。换句话说，交互器不是自适应的。

点A到直线ax + by + c = 0的投影是直线上距离A最近的点。

输入输出数据格式：
- 输入：
- 第一行包含一个整数t（1 ≤ t ≤ 50）——测试案例的数量。
- 每个测试案例的第一行包含一个整数n（2 ≤ n ≤ 25）——隐藏点的数量。
- 对于每个测试案例，保证任意两个隐藏点的x坐标至少相差1。类似地，任意一对点的y坐标也至少相差1。
- 所有隐藏点的坐标x和y的绝对值不超过100。
- 交互：
- 要查询直线ax + by + c = 0，你应该打印"? a b c"，其中a、b和c都是绝对值不超过100的实数。为了减少精度问题，a和b必须满足条件|a| + |b| ≥ 0.1。
- 作为对查询的响应，你将获得n个点，形式为"x1 y1 ... xn yn"，其中(x_i, y_i)是直线ax + by + c = 0上的投影点。保证每个打印出的点距离实际投影点的距离不超过10^-4。每个坐标最多打印9位小数。
- 如果查询次数过多，你将得到"Wrong answer"。
- 输出答案时，你应该打印"! x1 y1 ... xn yn"，其中(x_i, y_i)是隐藏点的坐标。你可以以任何顺序输出隐藏点。如果每个打印出的点与相应隐藏点的距离不超过10^-3，则答案被认为是正确的。打印答案不计入查询次数。
- 打印查询或答案后，别忘了输出换行符并刷新输出。否则，你将得到"Idleness limit exceeded"。

请注意，这里提供的翻译仅用于帮助理解题目大意和输入输出数据格式，具体细节和编程实现需要参考原文。题目大意：这是一个交互式问题。在二维欧几里得平面上有n个具有实坐标的不同隐藏点。你可以通过一次查询询问一条直线ax + by + c = 0，并获得所有n个点对此直线的投影，以某种顺序给出。提供的投影并非精确值，请阅读交互部分以获得更清晰的信息。 使用最少的查询次数，猜测所有n个点并以某种顺序输出它们。这里的“最少”意味着解决任意具有n个点的测试案例所需的最小查询次数。 隐藏点事先固定，不会在交互过程中改变。换句话说，交互器不是自适应的。 点A到直线ax + by + c = 0的投影是直线上距离A最近的点。 输入输出数据格式： - 输入： - 第一行包含一个整数t（1 ≤ t ≤ 50）——测试案例的数量。 - 每个测试案例的第一行包含一个整数n（2 ≤ n ≤ 25）——隐藏点的数量。 - 对于每个测试案例，保证任意两个隐藏点的x坐标至少相差1。类似地，任意一对点的y坐标也至少相差1。 - 所有隐藏点的坐标x和y的绝对值不超过100。 - 交互： - 要查询直线ax + by + c = 0，你应该打印"? a b c"，其中a、b和c都是绝对值不超过100的实数。为了减少精度问题，a和b必须满足条件|a| + |b| ≥ 0.1。 - 作为对查询的响应，你将获得n个点，形式为"x1 y1 ... xn yn"，其中(x_i, y_i)是直线ax + by + c = 0上的投影点。保证每个打印出的点距离实际投影点的距离不超过10^-4。每个坐标最多打印9位小数。 - 如果查询次数过多，你将得到"Wrong answer"。 - 输出答案时，你应该打印"! x1 y1 ... xn yn"，其中(x_i, y_i)是隐藏点的坐标。你可以以任何顺序输出隐藏点。如果每个打印出的点与相应隐藏点的距离不超过10^-3，则答案被认为是正确的。打印答案不计入查询次数。 - 打印查询或答案后，别忘了输出换行符并刷新输出。否则，你将得到"Idleness limit exceeded"。 请注意，这里提供的翻译仅用于帮助理解题目大意和输入输出数据格式，具体细节和编程实现需要参考原文。