WCWBTT

이 문제는 대화형 문제이다.

정점 1을 루트로 하는 루트 트리를 관리해야 한다. 트리에는 $n$개의 정점이 있으며, 정점 $i$ ($2 \le i \le n$)의 부모는 $p_i$ ($1 \le p_i < i$)이다.

$q$개의 쿼리를 처리해야 하며, 각 쿼리는 다음 두 형태 중 하나이다.

• ? $a$ $b$: $a$에서 $b$까지 가는 유일한 단순 경로 위에 있는 모든 정점의 집합 $S$를 출력한다.
• = $a$ $b$: $a$의 부모를 $b$로 바꾼다($p_a \leftarrow b$). 변경 후에도 정점들이 트리를 이루도록 보장되지만, $b < a$라는 보장은 없다.

그런데 곧 문제가 드러난다. 집합 $S$의 크기가 너무 커서 쿼리마다 모든 원소를 출력할 수 없다.

이를 해결하기 위해 정수 집합을 유지하고 빠르게 연산하는 특수한 컴퓨터를 설계했다. 이 컴퓨터가 처음 가진 것은 $n+1$개의 집합 $S_0, S_1, \ldots, 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| + |S_b|$이다.
• ! $k$ $x_1$ $x_2$ $\ldots$ $x_k$: $S_{x_1} \cup S_{x_2} \cup \cdots \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$)가 주어진다.

다음 줄에는 정수 $p_2, p_3, \ldots, p_n$ ($1 \le p_i < i$)이 주어지며, 이는 각 정점의 초기 부모이다.

샘플 입출력은 대화 방식을 보여 주기 위한 것이다. 빈 줄과 출력 비우기 표시는 읽기 편의를 위한 것이므로 출력하면 안 된다.

그림은 샘플 테스트 케이스에 해당한다.

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