5759：Gardener Bo

Gardener Bo loves Trees.Now he asks you to help him take care of his lovely tree.

A rooted tree with root=1 is given.Every node on the tree has a value $w_i$.Let $fa[u]$ be the father of $u$.

Let $LCA(u,v)$ be the least common ancestor of $u$ and $v$.The expression $[condition]$ is 1 when $condition$ is True,is 0 when $condition$ is False.

Define

\[f(u)=\sum_{i=1}^n\sum_{j=i}^n(w_i+w_j)*[LCA(i,j)=u]\]

Now there are $Q$ events happening.Each event has one of two types:

$1~u~x$:pick out all $v$ that satisfies $v=u$ or $fa[v]=u$ or $fa[fa[v]]=u$,and add $x$ to $w_v$.

$2~u$:query $f(u)\bmod 2^{32}$.

There are several test cases.

The first line contains two integers $n,Q$.

The second line contains $n-1$ integers,i-th indicates $fa[i+1]$.

The third line contains $n$ integers,the i-th indicates the initial $w_i$.

Following $Q$ lines each describes an event.

$1\leq n,Q\leq 3\times 10^5,|w_i|,|x|<10^9$

For every event with type 2,you should print a number indicating the answer.