I. Magic Tree
time limit per test
1 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a rooted tree consisting of $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$ and vertex $$$1$$$ is the root of the tree. The depth of vertex $$$1$$$ is $$$1$$$.

A tree is a connected undirected graph with $$$n - 1$$$ edges.

Now there are $$$q$$$ tasks that you need to do, and the $$$i$$$-th task is one of the following three types:

  • $$$1$$$ $$$x$$$ $$$(\ 2 \le x \lt n + i\ )$$$ — Add a new vertex numbered $$$n + i$$$ between vertex $$$x$$$ and its parent vertex.

  • $$$2$$$ $$$x$$$ $$$(\ 2 \le x \lt n + i\ )$$$ — Delete the vertex $$$x$$$ and turn all child vertex of $$$x$$$ into the child vertex of its parent vertex.

  • $$$3$$$ $$$x$$$ $$$(\ 1 \le x \lt n + i\ )$$$ — Query the depth of the vertex $$$x$$$.

It is guaranteed that the vertex $$$x$$$ must exist in the current tree.

Input

The first line of the input contains two integers $$$n, q$$$ $$$(2 \le n \le 2 \times 10^5, 1 \le q \le 2 \times 10^5)$$$.

The second line contains $$$n - 1$$$ integers $$$p_2, p_3, ..., p_n$$$ — the parents of vertices from the second to the $$$n$$$-th $$$(1 ≤ p_i \lt i)$$$.

The next $$$q$$$ lines each line contains two integers, and the $$$i$$$-th line belongs to one of the three types mentioned above.

It is guaranteed that there has at least one query task.

Output

For each query task, you should output one line containing an integer.

Example
Input
6 5
1 1 3 3 3
3 4
1 3
3 4
2 3
3 4
Output
3
4
3