很久以前，在 Xordic 诸国的心脏地带，住着一位名叫 Ronni 的勇敢士兵。Ronni 以其勇气和敏锐的头脑而闻名，经常能解开连最睿智的圣贤都感到困惑的谜题。有一天，Ronni 被召唤到一座神秘树木所在的古老森林。这棵树并非普通的树——它是完全隐形的，其节点和分支隐藏在凡人的视线之外。树的每个节点上都坐着一位古老的灵魂，而每个节点的度数掌握着理解这棵树结构的关键。
王国的神谕，被称为 Xoracle，是一个强大的实体，只能回答一种类型的查询： “告诉我节点 A 和节点 B 度数的按位异或值。”
掌握了这些神秘知识后，Ronni 必须推导出树中所有 $N$ 个节点的度数，以征服古老的灵魂并揭示树的秘密。然而，Xoracle 在封印其智慧之前最多只能回答 $Q$ 次查询。
Ronni 的任务是利用 Xoracle 的响应确定隐形树中所有节点的度数。这棵树有 $N$ 个节点和 $N - 1$ 条边，且是连通的，这意味着任意两个节点之间都存在路径。节点的度数是连接到该节点的边的数量。通过策略性地选择节点对并解读它们度数的按位异或值，Ronni 旨在重建树中所有节点的度数。
交互
你的程序应首先读取一行，包含两个空格分隔的整数 $N$ 和 $Q$，分别表示树的节点数和允许向 Xoracle 询问的最大查询次数。树的节点编号从 $1$ 到 $N$。
之后，你的程序最多可以进行 $Q$ 次查询。要进行查询，你的程序应输出一行格式为 "? i j"（不含引号）的内容，其中 $1 \le i, j \le N$。评测机随后将在一行中返回一个数字 $x$，其中 $x = \text{deg}(i) \oplus \text{deg}(j)$。这里 $\text{deg}(x)$ 是节点 $x$ 的度数，$\oplus$ 定义为按位异或。
两个整数 $a$ 和 $b$ 的按位异或运算是通过查看 $a$ 和 $b$ 的二进制表示来计算的。如果 $a$ 的第 $i$ 位和 $b$ 的第 $i$ 位中恰好有一个为 $1$，则结果的第 $i$ 位为 $1$，否则为 $0$。在 C++ 和 Python 中，该运算符均为 ^。
查询结束后，你的程序必须输出所有节点的度数。这通过输出新的一行 "!"（不含引号），后跟一个空格和 $N$ 个空格分隔的整数（即 $N$ 个节点的度数，顺序不限）来完成。
这不计入你的程序允许进行的查询次数。
为了接收查询的答案，并在最后提交度数，你的程序应刷新输出。这可以通过以下方式之一完成：
C++: std::cout << std::endl;
Python: print("", flush=True)
数据范围
- $2 \le N \le 10^5$
子任务
- (8 分) 任何节点的度数最大为 3。至少存在 1 个度数为 1、2 和 3 的节点。$N \le 1000$，$Q = N - 1$。
- (5 分) 任何节点的度数最大为 4。树中至少出现了 4 种可能度数中的 3 种。$N \le 1000$，$Q = N - 1$。
- (9 分) $Q = N^2$，$N \le 300$。
- (11 分) $Q = 35000$，$N \le 1000$。
- (24 分) $Q = N - 1$，$N \le 1000$。
- (43 分) $Q = N - 1$。
样例
样例 1
观察图 1 所示的树。
考虑以下交互，其中 > 表示评测机，< 表示选手程序。
> 4 3 < ? 2 4 > 0 < ? 4 1 > 2 < ? 3 3 > 0 < ! 1 3 1 1
- 首先给出数字 $N$ 和 $Q$。
- 然后对节点 2 和 4 进行查询，得到结果 0。
- 然后对节点 4 和 1 进行查询，得到结果 2。
- 然后对节点 3 和 3 进行查询，得到结果 0。
- 最后，程序回答树的度数为 1, 3, 1, 1，这是正确的。
（注意，度数可以以任何顺序给出。）
图 1：示例树 1
样例 2
观察图 2 所示的树。
考虑以下交互，其中 > 表示评测机，< 表示选手程序。
> 5 4 < ? 1 2 > 3 < ? 1 3 > 1 < ? 2 3 > 2 < ? 1 4 > 3 < ! 3 1 1 1 2
图 2：示例树 2
示例中给出的查询可能无法推导出正确答案。