CHOICE

Woohyeon is moving around on a tree. The tree has $N$ vertices, and vertex $1$ is the root. Initially, Woohyeon is at vertex $1$.

Some vertices are chosen by Woohyeon. Thus, each vertex is in one of two states: selected or not selected.

Woohyeon is given $Q$ queries of the following types.

• $1\ x$: Move Woohyeon to vertex $x$. Vertex $x$ is adjacent to his current vertex.
• $2\ x$: Flip the states of all descendants of vertex $x$. Every selected vertex becomes not selected, and every not selected vertex becomes selected.
• $3$: Print the distance from Woohyeon's current vertex to the closest selected vertex. If no vertex is selected, print .

Here, a descendant of vertex $x$ is any vertex from which $x$ can be reached by moving toward the root zero or more times. In particular, vertex $x$ is its own descendant.

Woohyeon is too busy moving around the tree to process the queries. Help him process them all!

The first line contains $N$ and $Q$, separated by a space. ($1 \le N,Q \le 300\,000$)

The second line contains $A_1,A_2,$. means vertex is initially selected, and means it is initially not selected. ()

For each query of type $3$, print the answer on its own line.

• $1 \le N, Q \le 300\,000$.
• $0 \le A_i \le 1$ ().