Description

有一个满二叉树，具有 $n$ 层（因此它恰好有 $2^n-1$ 个节点）。每个节点都有一个从 $1$ 到 $2^n-1$ 的整数 ID，这 $2^n-1$ 个 ID 形成一个从 $1$ 到 $2^n-1$ 的排列，但你并不知道具体的排列。

你需要通过最多 $4800$ 次查询找到这 $2^n-1$ 个节点的 ID。

Input Format

第一行包含一个整数 $n(1\leq n\leq 10)$，表示满二叉树的层数。

为了进行一次查询，你需要选择两个节点，其 ID 为 $u,v(1\leq u,v\leq 2^n-1)$，并输出如下格式的一行：

"? u v"

之后，你将收到：

"t"

即 $u$ 和 $v$ 的最近公共祖先的 ID。

你最多可以进行 $4800$ 次查询。

如果你已经找到了树的结构，输出如下格式的一行：

"! $f_1\ f_2\ f_3\ f_4$ ... $f_{2^n-1}$"

其中 $f_i$ 表示第 $i$ 个节点的父节点的 ID。如果没有父节点，则 $f_i=-1$。

在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到「Idleness Limit Exceeded」的判定。为此，请使用：

fflush(stdout) 或 cout.flush() 在 C++ 中；

System.out.flush() 在 Java 中；

stdout.flush() 在 Python 中。

此任务中的交互器不是自适应的。

2

3

3

3

? 1 2

? 2 3

? 1 3

! 3 3 -1

Hint

在这个例子中，树的根是 $3$，它的两个儿子是 $1$ 和 $2$。

对于任何查询 "? a b"，如果 $a eq b$，评测系统将返回答案 $3$。

因此我们找到了树的根是 $3$。（由 ChatGPT 4o 翻译）