WCWBTT

This is an interactive problem.

You need to maintain a rooted tree with vertex $1$ as the root. The tree has $n$ vertices, and the parent of vertex $i$ ($2 \le i \le n$) is $p_i$ ($1 \le p_i < i$).

You have to process $q$ queries, each in one of the following forms:

• ? $a$ $b$: Output the set $S$ of all vertices on the unique simple path from $a$ to $b$.
• = $a$ $b$: Change the parent of $a$ to $b$ ($p_a \leftarrow b$). The vertices are guaranteed to still form a tree after the change, but $b<a$ is not guaranteed.

The set $S$ can be too large to print every element in each query.

To deal with this, a special computer maintains sets of integers and operates on them quickly. Initially the computer has only $n+1$ sets $S_0, S_1, \ldots, S_n$, where $S_0 = \varnothing$ and $S_i = \{i\}$ for $1 \le i \le n$.

The computer supports only two operations.

• + $a$ $b$: Construct a new set $S_c = S_a \cup S_b$ with $S_a \cap S_b = \varnothing$. The new ID $c$ is one more than the maximum ID of all sets. The cost is $|S_a| + |S_b|$.
• ! $k$ $x_1$ $x_2$ $\ldots$ $x_k$: Print $S_{x_1} \cup S_{x_2} \cup \cdots \cup S_{x_k}$ as the answer. You must ensure $S_{x_i} \cap S_{x_j} = \varnothing$ for all $1 \le i < j \le k$. The cost is $k$.

The following limits apply.

• The cost of each operation cannot exceed $7000$.
• The total cost of all operations cannot exceed $7.5 \cdot 10^7$.
• The total number of operations cannot exceed $5 \cdot 10^6$.

The first line contains two integers $n$ and $q$ ($1 \le n \le 2 \cdot 10^5$, $1 \le q \le 2.5 \cdot 10^4$).

The next line contains $n-1$ integers $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$), the initial parent of each vertex.

The sample input and output only illustrate the interaction protocol. The blank lines and flush markers are there for readability, and you should not print them.

The figure corresponds to the sample test case.

• $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\}$