F. Yet Another Tree Problem
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes (the nodes are indexed from $$$1$$$ to $$$n$$$) that is rooted at node $$$1$$$.

Each node has a distinct value $$$a_i$$$ written on it. Let us define $$$Sub(u)$$$ to be the set of all nodes that are in the subtree of node $$$u$$$ (node $$$u$$$ is also included in its subtree).

You have to process $$$Q$$$ queries of $$$4$$$ different types. They are as follows:

  • 1 p u val: Create a new node with index $$$u$$$,parent $$$p$$$ and assign $$$A_u :=$$$ val.It is guaranteed that $$$u$$$ has not appeared before;
  • 2 u: Remove all $$$v$$$ such that $$$v \in Sub(u)$$$ from tree (remove all the nodes in the subtree of $$$u$$$);
  • 3 u val: Assign the value $$$A_u := $$$val;
  • 4 u: Print $$$mex_{v \in Sub(u)} A_v$$$. (Print the $$$mex$$$ of all values of nodes in the subtree of $$$u$$$).

    It is guaranteed that, at any time, there are no two distinct nodes in the tree that have the same value.

    Note: The $$$mex$$$ of a collection of integers $$$c_1, c_2, \ldots, c_k$$$ is defined as the smallest non-negative integer $$$x$$$ which does not occur in the collection $$$c$$$.

Input

The first line contains two space separated integers denoting $$$n,q (2 \le n,q \le 2 \cdot 10^5)$$$.

The next line contains $$$n-1$$$ space separated integers $$$p_2, p_3, \dots, p_n(1 \le p_i \le n)$$$ where $$$p_i$$$ denotes an edge between node $$$p_i$$$ and $$$i$$$ where $$$p_i$$$ is the parent of $$$i$$$.

The next line contains $$$n$$$ space separated integers $$$a_1, a_2, \dots, a_n(0 \le a_i \le 10^9)$$$.

The next $$$q$$$ lines contain the queries as described above.

It's guaranteed:

  • The edges of the initial graph form a valid tree.
  • $$$0 \le$$$ val $$$\le 10^9$$$
  • In queries, $$$1 \le p, u \le n+q$$$
  • At all times there are no two distinct nodes in the tree that have the same value.
  • For all $$$p, u$$$ that appear in the queries of type $$$1$$$, there is a node with index $$$p$$$ in the tree,there is no node with the index $$$u$$$ and $$$u$$$ has not appeared before.
  • For all $$$u$$$ that appear in the queries of type $$$2, 3$$$ and $$$4$$$, there is a node with index $$$u$$$ in the tree.
Output

For each query of type $$$4$$$, print the answer in a new line.

Example
Input
5 5
1 2 3 3
5 4 3 2 1
1 5 7 0
4 5
2 3
3 2 0
4 2
Output
2
1
Note
  • Initially, the tree looks like this:

  • After the first query, the tree looks like this:

  • After the fourth query, the tree looks like this:

  • After the fifth query, the tree looks like this: