发送 GCD

英文题名：G. Send GCDs
来源：Codeforces 2237G
比赛：Order Capital Round 2 (Codeforces Round 1104, Div. 1 + Div. 2)
时间限制：3 seconds
空间限制：256 megabytes

【33DAI 很懒，还没配这题的数据，只配了 first，需要配完整题目时可以找 33DAI】

题目描述

这是一道双运行通信题。第一次运行时得到原数组 $a$，需要构造数组 $b$；第二次运行时只能询问 $b_i,b_j$ 的最大公约数，并最终还原 $a$。

输入格式

第一次运行输入以 first 开头，随后给出 $a$；第二次运行输入以 second 开头，随后通过交互询问恢复数组。

输出格式

第一次输出构造的 $b$；第二次按交互协议输出询问 ? i j 和最终答案 ! a_1 ... a_n。

样例

first
2
6
1 1 4 5 1 4
3
2 6 10

7
20 1 1 4 5 1 4
4
30 2 6 10

second
2
3 4

2

6

10
6 7

1

1

4

5

1

4

? 1 2

? 1 3

? 1 4

! 2 6 10

? 1 2

? 1 3

? 1 4

? 1 5

? 1 6

? 1 7

! 1 1 4 5 1 4