这是一个交互式问题。
你需要维护一棵以顶点 1 为根的有根树。该树有 $n$ 个顶点，顶点 $i$ ($2 \le i \le n$) 的父节点为 $p_i$ ($1 \le p_i < i$)。
你需要处理 $q$ 次查询，每次查询属于以下形式之一：
- “? a b”：输出集合 $S$，其中 $S$ 是从 $a$ 到 $b$ 的唯一简单路径上所有顶点组成的集合。
- “= a b”：将 $a$ 的父节点修改为 $b$（即 $p_a \leftarrow b$）。保证修改后顶点仍然构成一棵树，但不保证 $b < a$。
但你很快发现了一个问题：集合 $S$ 的大小可能太大，你无法在每次查询中输出所有元素。
为了解决这个问题，你设计了一台特殊的计算机。这台计算机可以维护整数集合并快速对其进行操作。最初，计算机只有 $n+1$ 个集合 $S_0, S_1, \dots, S_n$，其中 $S_0 = \varnothing$，且对于所有 $1 \le i \le n$，有 $S_i = \{i\}$。
这台计算机既高效又简单：它只支持两种不同的操作！
- “+ a b”：构造一个新集合 $S_c = S_a \cup S_b$（满足 $S_a \cap S_b = \varnothing$），其中 $c$ 为当前所有集合 ID 的最大值加 1。你必须确保 $S_a \cap S_b = \varnothing$。该操作的代价为 $|S_a| + |S_b|$。
- “! k x1 x2 . . . xk”：输出集合 $S_{x_1} \cup S_{x_2} \cup \dots \cup S_{x_k}$ 作为查询的答案。你需要确保对于所有 $1 \le i < j \le k$，满足 $S_{x_i} \cap S_{x_j} = \varnothing$。该操作的代价为 $k$。
现在，你需要使用这台计算机来维护这棵有根树。为了避免计算消耗过多时间并对计算机造成损坏，使用计算机时有以下限制：
- 每次操作的代价不能超过 7000。
- 所有操作的代价总和不能超过 $7.5 \cdot 10^7$。
- 操作总次数不能超过 $5 \cdot 10^6$。
输入格式
第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 2 \cdot 10^5, 1 \le q \le 2.5 \cdot 10^4$)。
下一行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ ($1 \le p_i < i$)，表示每个顶点的初始父节点。
交互
交互库将执行 $q$ 次查询。每次查询包含一行，形式为“? a b”或“= a b”。这些形式如上所述。在每次查询后，你可以执行任意多次操作。
特别地，在查询“? a b”之后，你需要执行一次操作“! k . . .”。在每次操作“! k . . .”之后，你需要刷新输出。
请注意，由于输出量巨大，我们建议你仅在每次操作“! k . . .”后刷新输出。
样例
输入 1
3 3 1 2 ? 2 3 = 3 1 ? 2 3
输出 1
+ 1 2 + 3 4 ! 2 2 3 + 1 2 + 1 3 ! 2 2 7
说明
样例输入和输出仅用于说明交互协议。字符串“”和空行仅为方便读者阅读而添加，你不应输出这些信息。
以下是样例测试用例的示意图：
该图对应样例测试用例
- $S_0 = \varnothing$
- $S_1 = \{1\}$
- $S_2 = \{2\}$
- $S_3 = \{3\}$
- $S_4 = \{1, 2\}$
- $S_5 = \{1, 2, 3\}$
- $S_6 = \{1, 2\}$
- $S_7 = \{1, 3\}$