F. Distances in a Subtree
time limit per test
5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree, consisting of $$$n$$$ vertices. The $$$1$$$-st vertex is the root; for every other vertex $$$i$$$, two integers $$$p_i$$$ and $$$w_i$$$ are given, which mean that the parent of the $$$i$$$-th vertex is $$$p_i$$$, and the edge connecting these two vertices has weight $$$w_i$$$. The distance between two vertices $$$d(x, y)$$$ is equal to the total weight of all edges on the simple path between them.

Each vertex $$$i$$$ has a color $$$c_i$$$. You need to process $$$q$$$ queries of $$$2$$$ types:

  1. v x — recolor vertex $$$v$$$ to color $$$x$$$, that is, assign $$$c_v := x$$$;
  2. v — consider all pairs of vertices $$$(x, y)$$$ in the subtree of vertex $$$v$$$ (including vertex $$$v$$$ itself) such that $$$x \ne y$$$, $$$c_x = c_y$$$, and vertex $$$x$$$ is an ancestor of vertex $$$y$$$. For all such pairs, compute the distance $$$d(x, y)$$$, and then output the minimum such distance, or $$$-1$$$ if there are no such pairs.
Input

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

The next line contains integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$), where $$$c_i$$$ is the color of vertex $$$i$$$.

The next line contains integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$), where $$$p_i$$$ is the parent of vertex $$$i$$$.

The next line contains integers $$$w_2, w_3, \dots, w_n$$$ ($$$1 \le w_i \le 10^9$$$), where $$$w_i$$$ is the weight of the edge between vertex $$$i$$$ and its parent $$$p_i$$$. The following $$$q$$$ lines contain the queries. Each query starts with two integers $$$t_i$$$ and $$$v_i$$$ ($$$1 \le t_i \le 2$$$; $$$1 \le v_i \le n$$$) — the type of the query and the index of the vertex it is applied to. If $$$t_i = 1$$$, the third integer $$$x_i$$$ ($$$1 \le x_i \le n$$$) follows.

Output

For each query of the second type, print one integer — the answer to it.

Example
Input
5 10
1 1 1 1 1
1 2 2 3
1 1 1 3
2 1
2 2
2 3
2 4
1 2 2
2 1
2 2
1 3 3
2 1
2 2
Output
1
1
3
-1
2
3
2
-1