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.

5 3
1 1 3 3
-5 2 0 7 -6
1 5 2
2 3
2 2
10 5
1 2 3 3 1 2 6 2 2 
-2 5 8 -6 0 -4 6 6 8 9
2 10
1 3 4
1 6 -2
2 9
2 4

6
4
18
16
4294967292

绍兴一中

2016 Multi-University Training Contest 3