Namunamu, Time to Plant Trees

Geunseong is fond of trees.

He is a developer now, but his love for trees has not faded. One day, while playing with binary trees, Geunseong realized that a binary tree is a tree yet bears no fruit, and he was deeply shocked. Insisting that trees must bear fruit, he built a tree graph that bears fruit and named it "Namunamu".

The features of Namunamu are as follows.

1. Vertex $1$ of the tree is the root. The tree grows upward from the root.
2. Vertices other than $1$ are the points where a branch forks or ends. A branch can be connected to a vertex. However, branches forked from different vertices do not merge at a vertex.
3. An edge is a branch. Both ends of a branch must be vertices.
4. A vertex can bear at most one fruit. The root bears no fruit. Before each query, every vertex that can bear fruit does bear fruit.

After building the tree, Geunseong came up with two kinds of queries.

• 1 i j w: (Grafting) Attach a branch to an arbitrary vertex $i$.
  • Vertex $i$ belongs to the same graph as the root.
  • Since a branch always ends at a vertex, the vertex numbered $j$ is created at the far end of the new branch.
  • Vertex $j$ bears a fruit of weight $w$. $w=0$ means no fruit grows there.
  • ($1 \le i, j \le N + M;$ $0 \le w \le 500$)
• 2 i: (Harvest) Output the force needed to shake vertex $i$ so that every fruit on vertex $i$ and on all vertices connected above it falls.
  • Shaking vertex $i$ shakes every branch and vertex connected above it with the same force.
  • To knock down all the fruit, the force must equal the sum of the fruit weights on vertex $i$ and on all vertices connected above it.
  • Shaking with force $0$ is not allowed, so if the total weight is $0$, output -1.
  • ($1 \le i \le N + M$)

The input values are all integers, and the input is guaranteed to be valid. There is at least one harvest query.

Geunseong left for the clubroom in the middle of writing these queries. Please solve them for him.

The first line contains the initial number of vertices $N$ and the number of queries $M$, separated by a space. The vertices initially have distinct numbers from $1$ to $N$. ($2 \le N, M \le 100\,000$)

The second line contains, for each vertex from $1$ to $N$, the vertex directly above it that it is connected to by a branch, separated by spaces. Vertex $1$ is the root, so it is given as -1. Every vertex eventually belongs to the same graph as the root, but some may not yet belong to it during the input.

The third line contains the fruit weight $w_i$ of each vertex from $1$ to $N$, separated by spaces. ($0 \le w_i \le 500$) A value of $0$ means no fruit grows there. The root bears no fruit.

The next $M$ lines each contain one query.

For each harvest query, output the force needed to shake the vertex. If that force is $0$, output -1.

The first sample starts with the initial tree shape. In the first query, shaking vertex $1$ also shakes vertices $2$ and $3$. Vertex $3$ holds a fruit that needs a force of $3$ to knock down, so the force is $3$.

This picture shows the tree after three grafts. Shaking vertex $4$ shakes only vertex $4$, and knocking down its fruit requires a force of $5$. Likewise, shaking vertex $7$ shakes vertices $7$, $4$, and $5$. Knocking down the fruit on vertices $4$ and $7$ requires a force of $9$.

In the second sample, the first query shakes vertex $1$, which also shakes vertices $2$, $3$, and $4$. None of them bears a fruit, so the force is $0$ and the output is -1.

Shaking vertex $1$ shakes vertices $2$, $3$, $4$, and $7$. Knocking down the fruit on vertex $7$ requires a force of $500$.