Path Sum A To B

hard

You are given a tree with n nodes (numbered from 1 to n), node 1 is the root of tree.
Each node has a value say Vi is the value of i'th node.

You have to perform q queries of two types:-
1 i v : change the value of i'th node to v,
2 a b  : add all nodes on path from a to b node including a and b.

Input Format

First line contains single integer n. second line contains n integers v1 v2 v3 .... vn third line contains n-1 integers p2 p3 p4 ... pn here pi is the parent of i'th node fourth line contains single int q q following lines contains queries of type 1 and 2 as mentioned above

Output Format

of every query of type 2 print sum of values.

Constraints

1. 1 &lt;= N &lt;= 10^5
2. 1 &lt;= Vi &lt;= 10^4
3. 1 &lt;= q &lt;= 10^4

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

8
4 7 9 5 2 1 3 5 
1 1 1 4 3 4 1 
7 
2 2 6
1 6 2
2 2 6
2 5 7
1 3 12
2 6 8
2 7 6

Output

Lca - Hld

Qtree - Query On A Tree