这是一个交互式问题。
最近,来自 Nibiru 星球(也称为 Not-Taking-It)的外星人决定入侵地球。作为 Nibiru 特种部队总部的指挥官,你正计划将第一批宇宙飞船降落在地球上最和平的国家——Byteland。
你知道 Byteland 的领土形状是一个平面上的 $n$ 边形(是的,Byteland 不大,所以我们可以将 Byteland 周围的表面视为平面的一部分)。该多边形的每个顶点代表一个城镇,每条边代表 Byteland 边界的一部分。当然,边界不能自交,且多边形的任意两条边仅在它们相邻时才有一个公共点(此时恰好有一个公共点)。
你的任务是求出 Byteland 的精确面积,以便计算部署在那里的宇宙飞船数量。然而,你并不知道 Byteland 的确切形状,因为发现它需要花费太长时间。幸运的是,Nibiru 情报局已经在 Byteland 的 $n$ 个城镇中各安插了一名间谍。每名间谍都有一盏巨大的信号灯。你还知道,间谍的编号为 $1$ 到 $n$,编号相邻的间谍(即编号差为 $1$ 或 $n-1$)位于由边界直接相连的城镇中。
你可以执行以下特殊操作:首先,你告诉每名间谍将他们的灯打开或关闭。然后,你派一名宇航员前往地球,她会看到所有亮着的灯,并告诉你包含这些灯的最小凸集的面积(换句话说,这些灯的凸包面积)。由于在太空中难以保持方向感,宇航员无法提供关于城镇位置的其他任何信息。
注意,如果你执行特殊操作的次数超过 $\frac{n(n-1)}{2}$ 次,Byteland 警方就会察觉到异常,入侵将失败。请在不引起过多注意的情况下求出 Byteland 的精确面积!
交互
首先,你将获得一个整数 $n$ ($3 \le n \le 200$),即代表 Byteland 的多边形的顶点数。
然后,你可以执行最多 $\frac{n(n-1)}{2}$ 次特殊操作。描述特殊操作的查询应包含两行: ? $k$ $a_1$ $a_2$ $\dots$ $a_k$
其中 $k$ ($3 \le k \le n$) 是需要打开灯的间谍数量,$a_1, \dots, a_k$ ($1 \le a_i \le n, a_i \neq a_j$ 当 $i \neq j$) 是这些间谍所在城镇的编号。所有其他城镇的间谍将关闭他们的灯。
执行查询后,你应该从输入中读取一行,其中包含一个非负数:亮灯的凸包面积(单位为平方米)。
当你认为你知道 Byteland 的面积 $x$ 时,打印 ! $x$
在单行上。打印答案不计入特殊操作次数。答案必须精确,不允许有任何误差,也不允许有前导零。之后,你的程序应正常终止。
请记住,在进行查询或打印答案后,请换行并刷新输出缓冲区。
保证多边形在程序执行期间不会改变,且多边形的面积严格大于零。此外,保证存在一个包含 Byteland 的平面笛卡尔坐标系,使得多边形所有顶点的坐标(以米为单位)均为 $[-10^9, 10^9]$ 范围内的整数。
样例
输入 1
3 0.5
输出 1
? 3 1 2 3 ! 0.5
说明
对于样例测试,Byteland 的城镇位于某个笛卡尔坐标系下的点 $(0, 0)$、$(0, 1)$ 和 $(1, 0)$。
注意,样例输入和输出中的空行仅为清晰起见而打印,实际并不存在。