题目背景

「欲买桂花同载酒，终不似，少年游。」

——刘过《唐多令·芦叶满汀洲》

清风想起了自己学完语法第一次接触算法的那天，当时他惊叹于最大子段和的线性做法的奇妙，居然不用暴力枚举每个区间。

“明月，我们能玩一个游戏吗？”

题目描述

明月现在想出了一个长度为 $n$ 的整数序列 $a$，对于任意 $1 \le i \le n$ 满足 $|a_i| \le 10^6$，这个序列在初始时已经完全确定。

明月只告诉了清风 $n$ 的值，清风现在可以提出最多 $10^4$ 个询问，每次询问给出一个区间 $[l,r]$，表示将 $a$ 序列区间内元素的值全都乘上 $-1$，之后明月告诉他操作完之后这个序列的最大子段和的值。而这个要求必须满足 $1 \le l \le r \le n$。操作的效果（对 $a$ 序列元素的改动）是永久保留的。

本题中序列的最大子段和的定义为选出序列中的一个可以为空的连续段使得元素的和最大，这个最大值即为这个序列的最大子段和。

而清风的目标就是还原这个序列的每个元素的初始值，清风可以进行最多一次作答。

假如你是清风，请完成这个游戏。注意你的得分和询问次数相关。

交互格式

第一行输入一个整数 $n$。

在此之后，你应该进行若干次询问，每次询问形如 $?\ l \ r$，表示给出一个区间 $[l,r]$，你需要保证 $1 \le l \le r \le n$。

如果你得到了答案，请你进行形如 $!\ a_1\ a_2\ a_3 \dots a_n$ 的回答，代表你得到了 $a$ 数组每个元素的初始值。你需要保证 $|a_i| \le 10^6$。在此之后你应该立即退出本轮交互。

每次输出后，请刷新缓冲区。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

特别的，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

每次询问并刷新缓冲区后，你将从标准输入中输入一个数字 $M$，表示序列 $a$ 的最大子段和。

输入格式

本题有多组数据。

第一行，一个整数 $T$ 表示数据组数。

对于每一组数据，请按照 【交互格式】 进行交互。当你报告 $a$ 序列每个位置的初始值后：

• 如果你给出的初值正确：
  • 如果这是最后一组数据，交互库退出根据询问次数打分；
  • 如果这不是最后一组数据，你应当接着读入 $n$ 以进行下一组数据的交互。
• 否则，初值错误，交互库会立刻终止，给你打 $0$ 分。
• 打分规则具体参见 【计分方式】 一节。

输出格式

见 【输入格式】。

1
5

3

2

? 1 3

? 1 3

! 1 -1 0 2 -2

提示

【样例 1 解释】

$a$ 序列的初始值为 $\{1,-1,0,2,-2\}$。

样例提供的交互过程不符合逻辑（也就是说凭这些信息猜不出 $a$ 的所有元素初值），只是演示交互格式而已。

【数据规模与约定】

本题采用捆绑测试。

对于每个测试点，$1 \le T \le 10$，$2 \le n \le 10^3$，$|a_i| \le 10^6$，且交互库不是适应性的，即 $a_i$ 的所有值在交互开始前已经全部生成。

• Subtask 1（20 pts）：$n \le 13$。
• Subtask 2（80 pts）：无特殊限制。

【计分方式】

• 如果你在一些测试点上出现 TLE / RE 等错误，你该子任务不得分。
• 对于每组数据：若你出现格式错误或询问次数超过 $10^4$，或答案不正确，则该组数据得分比率为 $0.0$。否则按照以下方式计分：
  • 记你在该组测试数据的询问次数为 $Q$；
  • 若 $Q \le 3001$，你得分比率为 $1.0$；
  • 若 $3001 < Q \le 3011$，则你的得分比率为 $1.0-\frac{Q-3001}{100}$；
  • 若 $Q>3011$，则你得分为 $0.9-\frac{Q-3011}{10000}$。
• 对于每个测试点，你的得分比率为该测试点所有数据的最小值；对于每个子任务，你的得分比率为该组子任务的每个测试点的最小值。
• 由于最终分数为整数，分数计算结果可能会被四舍五入，但是保证较多次数对应得分比率一定不比较少次数对应比率的测试数据得分高。

【后记】

“希望未来的道路上，你们的脆弱永远都有人能够包容；你们说的话，永远都有人能聆听。”

“大家的十里春风，永远都有人能懂。”