题目描述

这是一道模板题。

给定一棵 $\red{n}$ 个节点的树，初始时该树的根为 $\red{1}$ 号节点，每个节点有一个给定的权值。下面依次进行 $\red{m}$ 个操作，操作分为如下五种类型：

• 换根：将一个指定的节点设置为树的新根。
• 修改路径权值：给定两个节点，将这两个节点间路径上的所有节点权值（含这两个节点）增加一个给定的值。
• 修改子树权值：给定一个节点，将以该节点为根的子树内的所有节点权值增加一个给定的值。
• 询问路径：询问某条路径上节点的权值和。
• 询问子树：询问某个子树内节点的权值和。

输入格式

第一行一个整数 $\red{n}$，表示节点的个数。

第二行 $\red{n}$ 个整数表示第 $\red{i}$ 个节点的初始权值 $\red{a_i}$。

第三行 $\red{n-1}$ 个整数，表示 $\red{i+1}$ 号节点的父节点编号 $\red{f_{i+1}\ (1 \leqslant f_{i+1} \leqslant n) }$。

第四行一个整数 $\red{m}$，表示操作个数。

接下来 $\red{m}$ 行，每行第一个整数表示操作类型编号：$\red{(1 \leqslant u, v \leqslant n)}$

• 若类型为 $\red{1}$，则接下来一个整数 $\red{u}$，表示新根的编号。
• 若类型为 $\red{2}$，则接下来三个整数 $\red{u,v,k}$，分别表示路径两端的节点编号以及增加的权值。
• 若类型为 $\red{3}$，则接下来两个整数 $\red{u,k}$，分别表示子树根节点编号以及增加的权值。
• 若类型为 $\red{4}$，则接下来两个整数 $\red{u,v}$，表示路径两端的节点编号。
• 若类型为 $\red{5}$，则接下来一个整数 $\red{u}$，表示子树根节点编号。

输出格式

对于每一个类型为 $\red{4}$ 或 $\red{5}$ 的操作，输出一行一个整数表示答案。

样例

样例输入

6
1 2 3 4 5 6
1 2 1 4 4
6
4 5 6
2 2 4 1
5 1
1 4
3 1 2
4 2 5

样例输出

15
24
19

数据范围与提示

对于 $\red{100\%}$ 的数据，$\red{1\leqslant n,m,k,a_i\leqslant 10^5}$。数据有一定梯度。