Gardener Bo

Problem Description

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}$.

Input

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$

Output

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

Sample Input

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

Sample Output

6
4
18
16
4294967292

Author

绍兴一中

Source

2016 Multi-University Training Contest 3