4389 - ZYB and Trees

最初有一棵带点权的树。 给出下列操作： 1 x y z 在x为根的树里，y到根路径链加z 2 x y z x~y链上点权都修改为z 3 x y 在x为根的树里，对y子树的点权求和 4 x y x~y链上取点权max 5 x y x~y链上求点权和 6 x y 连接 x~y 7 x y 断开 x~y

保证操作1~5上x和y在同一棵树上。 保证6和7操作合法（即操作前后都是森林）。

Input

第一行一个数N。 第二行N个数表示最开始N个数的权值。 接下来N-1行，每行一个数xi。第i行表示xi和i+1有一条边。 接下来一个数M表示操作数。 接下来M行每行3个或4个数，形式如上。 N,M<=200000 1<=x,y<=N 1<=z<=500000 一共有4组数据。不卡常数。

Output

对于每一个3~5操作输出答案。 保证结果不超过long long。

Examples

Input

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

Output

1
1
2
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题