Break And Fix The Tree

 Chef is playing a game, and to win the prize, he must complete it. But he is busy arranging meals for the vortex party, so he asked you the play the game in his place. The game is as below:

You are given a rooted tree of size N$N$ rooted at node 1$1$, where each node i$i$ has a value Vi$V_i$ assigned to it. Define Pu$P_u$ as the parent of node u$u$. You have to perform queries of the following type on the tree:

1. 1XW$1XW$: Break the edge between node X$X$ and PX$P_X$ in the tree, and attach X$X$ as a child of W$W$ (note that this means PX=W$P_X=W$ after this operation). It is guaranteed that X$X$ is a leaf node of the tree.
2. 2XK$2XK$: Change the value on node X$X$ to K$K$ (i.e. assign VX←K$V_X\leftarrow K$).
3. 3XY$3XY$: Calculate the sum of values of nodes on the path from X$X$ to Y$Y$.

Note that the queries are accumulative, meaning the changes made in each query is persisted for the following queries.

Input Format

• The first line of the input contains an integer N$N$ - the number of nodes in the tree.
• The next line contains N−1$N-1$ space-separated integers P2,P3,…,PN$P_2,P_3,\dots ,P_N$ - the parents node of 2$2$ to N$N$.
• The next line contains N$N$ space-separated integers V1,V2,…,VN$V_1,V_2,\dots ,V_N$ - the initial values of the nodes.
• The next line contains an integer Q$Q$ - the number of queries.
• Each of the next Q$Q$ lines contains a query as described in the statement.

Output Format

For each query of type 3$3$, output on a new line the sum of values of nodes on the path from X$X$ to Y$Y$.

Constraints

• 2≤N≤105$2\le N\le {10}^5$
• 1≤Pi≤N$1\le P_i\le N$
• −109≤Vi≤109$-{10}^9\le V_i\le {10}^9$
• 1≤Q≤105$1\le Q\le {10}^5$
• 1≤X,Y,W≤N$1\le X,Y,W\le N$
• X≠W$X\ne W$
• −109≤K≤109$-{10}^9\le K\le {10}^9$

Sample Input 1 

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

Sample Output 1 

11
20

Explanation

• Initially, the tree is

• For first query, the path followed is 4→2→5$4\to 2\to 5$. Therefore the sum of values is 4+2+5=11$4+2+5=11$.
• After updating the tree according to second query, it becomes

• After updating the tree according to third query, it becomes

  

• After updating the tree according to fourth query, it becomes

  

• After updating the tree according to fifth query, it becomes

  

• The path for the sixth query is 2→4→3→5$2\to 4\to 3\to 5$. Therefore the sum of values is 2+10+3+5=20$2+10+3+5=20$.