You have a root tree containing $*n*$ vertexes. Let's number the tree vertexes with integers from $1$ to $*n*$. The tree root is in the vertex $1$.

Each vertex (except fot the tree root) $*v*$ has a direct ancestor $*p*_{*v*}$. Also each vertex $*v*$ has its integer value $*s*_{*v*}$.

Your task is to perform following queries:

• P $*v*$ $*u*$ ($*u* ≠ *v*$). If $*u*$ isn't in subtree of $*v*$, you must perform the assignment $*p*_{*v*} = *u*$. Otherwise you must perform assignment $*p*_{*u*} = *v*$. Note that after this query the graph continues to be a tree consisting of $*n*$ vertexes.
• V $*v*$ $*t*$. Perform assignment $*s*_{*v*} = *t*$.

Your task is following. Before starting performing queries and after each query you have to calculate expected value written on the lowest common ancestor of two equiprobably selected vertices $*i*$ and $*j*$. Here lowest common ancestor of $*i*$ and $*j*$ is the deepest vertex that lies on the both of the path from the root to vertex $*i*$ and the path from the root to vertex $*j*$. Please note that the vertices $*i*$ and $*j*$ can be the same (in this case their lowest common ancestor coincides with them).

Input

The first line of the input contains integer $*n*$ ($2 ≤ *n* ≤ 5·10^{4}$) — the number of the tree vertexes.

The second line contains $*n* - 1$ integer $*p*_{2}, *p*_{3}, ..., *p*_{*n*}$ ($1 ≤ *p*_{*i*} ≤ *n*$) — the description of the tree edges. It is guaranteed that those numbers form a tree.

The third line contains $*n*$ integers — $*s*_{1}, *s*_{2}, ... *s*_{*n*}$ ($0 ≤ *s*_{*i*} ≤ 10^{6}$) — the values written on each vertex of the tree.

The next line contains integer $*q*$ ($1 ≤ *q* ≤ 5·10^{4}$) — the number of queries. Each of the following $*q*$ lines contains the description of the query in the format described in the statement. It is guaranteed that query arguments $*u*$ and $*v*$ lie between $1$ and $*n*$. It is guaranteed that argument $*t*$ in the queries of type V meets limits $0 ≤ *t* ≤ 10^{6}$.

Output

Print $*q* + 1$ number — the corresponding expected values. Your answer will be considered correct if its absolute or relative error doesn't exceed $10^{ - 9}$.

Note

Note that in the query P $*v*$ $*u*$ if $*u*$ lies in subtree of $*v*$ you must perform assignment $*p*_{*u*} = *v*$. An example of such case is the last query in the sample.