You have a rooted tree with vertices, each assigned a value a_x. The root is node .
You can perform operations where you merge two adjacent nodes and into a single node , with the value of being equal to the minimum value between the two nodes. This operation changes edges connected to or to be connected to . The cost of this operation is |a_x - a_y|. The total cost of multiple operations is the sum of individual operation costs.
For queries, you have two types:
: This updates the value of node to .
: This asks for the minimum cost of operations to reduce the subtree rooted at to just one node.
The first line contains a single integer (1 \le n \le 200\,000), the number of vertices.
The second line contains integers a_1, a_2, \dots, a_n (1 \le a_i \le 10^9), representing the assigned values of each node.
The third line contains n-1 integers p_2, p_3, \dots, p_n (1 \leq p_i \leq n), representing the parent of each node.
The fourth line contains one integer (1 \le q \le 200\,000), representing the total number of queries.
The following lines each contain a query:
Either (1 \leq x \leq n, 1\leq y \leq 10^9), or (1\leq x \leq n).
On each line of the input, you need to print the result of a query of type , in the same order as the order from the input.
Example 1
Example 2
( points) n \le 1000, q=1;
( points) q=1;
( points) the tree is a chain and there are only queries of the second type;
( points) there are only queries of the second type;
( points) p_i=1;
( points) no additional constraints.