Remove Node#402

Remove Node

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:

Input

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).

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Scoring

  1. ( points) n \le 1000, q=1;

  2. ( points) q=1;

  3. ( points) the tree is a chain and there are only queries of the second type;

  4. ( points) there are only queries of the second type;

  5. ( points) p_i=1;

  6. ( points) no additional constraints.