你独自困在小屋里，外面下着雨。你感到百无聊赖，唯一能用来消磨时间的是一副记忆卡牌。独自玩记忆游戏并不怎么有趣，但你开发了一种单人变体玩法，它不仅需要良好的记忆力，还需要策略。

游戏规则如下：你有一副洗好的 $n$ 张牌，其中 $n$ 为偶数，每张牌上写有一个 $1$ 到 $n/2$ 之间的数字。每个数字恰好有两张牌。这些牌面朝下放在桌子上，你的目标是找出每张牌上写的数字。在一次操作中，你拿起两张牌。在揭开它们之前，你会随机洗这两张牌，这样你就不知道哪张牌原本在哪里。然后你查看这两张牌。之后，在把它们放回原位之前，你会再次将它们面朝下洗牌。这样，你就知道了这两张牌的数字以及它们的位置，但不知道哪张牌最终落在了哪个位置，甚至不知道最初哪张牌来自哪个位置。

你的任务是编写一个程序来赢得这个游戏。

交互

这是一个交互式问题。你的提交将针对一个交互器运行，该交互器读取你的程序的标准输出并向你的程序的标准输入写入内容。此交互需要遵循特定的协议：

• 交互器首先发送一个整数 $n$ ($2 \le n \le 10^5$，$n$ 为偶数)。只有在样例中 $n$ 才不等于 $10^5$。
• 你的程序随后重复发送两个整数 $x$ 和 $y$ ($1 \le x, y \le n, x \neq y$)，并在前面加上 “?”。
• 交互器回复两个整数 $a$ 和 $b$ ($1 \le a, b \le n/2$)，表示在查询后，要么第 $x$ 张牌是 $a$ 且第 $y$ 张牌是 $b$，要么第 $x$ 张牌是 $b$ 且第 $y$ 张牌是 $a$。
• 当你准备好输出答案时，打印 “!”，后跟 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $a_i$ 是输出时第 $i$ 张牌上的数字。

你最多可以使用 $92\,000$ 次操作。打印答案不计入操作次数。

交互器不是自适应的。牌的初始位置由交互器在任何交互发生前确定。当你进行操作时，这两张牌在向你展示之前以及放回原处之前，都会由交互器进行均匀随机洗牌。保证牌的初始布局是 $1, 1, 2, 2, \dots, n/2, n/2$ 的一个随机排列。

你的提交将在正好 $100$ 个测试用例上运行，每个测试用例都有 $n = 10^5$。

确保在每次写入后刷新缓冲区。

提供了一个测试工具来帮助你开发解决方案。

样例

样例 1

6
? 2 1
3 2
? 5 3
2 3
? 6 4
1 1
? 1 3
3 3
! 3 2 3 1 2 1

A log cabin