Problem: 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 pv. Also each vertex v has its integer value sv. 

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 pv = u. Otherwise you must perform assignment pu = v. Note that after this query the graph continues to be a tree consisting of n vertexes.
  * V v t. Perform assignment sv = 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·104) — the number of the tree vertexes. 

The second line contains n - 1 integer p2, p3, ..., pn (1 ≤ pi ≤ n) — the description of the tree edges. It is guaranteed that those numbers form a tree.

The third line contains n integers — s1, s2, ... sn (0 ≤ si ≤ 106) — the values written on each vertex of the tree.

The next line contains integer q (1 ≤ q ≤ 5·104) — 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 ≤ 106.

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.

Examples

Input

5
1 2 2 1
1 2 3 4 5
5
P 3 4
P 4 5
V 2 3
P 5 2
P 1 4


Output

1.640000000
1.800000000
2.280000000
2.320000000
2.800000000
1.840000000

Note

Note that in the query P v u if u lies in subtree of v you must perform assignment pu = v. An example of such case is the last query in the sample.

Solution (in JAVA):

Solution:
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Locale;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    static class Query {
        int kind;
        Vertex v;
        Vertex u;
        int t;
    }

    static class Vertex {
        long s;
        long subtreeSize;
        boolean hasInterestingInSubtree = false;
        long subtreeAnswer;
        long childSquareSum;
        Vertex parent;
        Vertex firstChild;
        Vertex nextSibling;
        Vertex interestingParent;
        Vertex firstInterestingChild;
        Vertex nextInterestingSibling;
        long multiplierForIntermediates;
        long constantForIntermediates;
        long intermediatesSize;
        long boringChildrenSize;
        long boringChildrenSquareSum;
        long boringChildrenAnswer;
        boolean interesting;

        void propagateInteresting() {
            Vertex v = firstChild;
            int numIntChild = 0;
            while (v != null) {
                v.propagateInteresting();
                if (v.hasInterestingInSubtree) ++numIntChild;
                v = v.nextSibling;
            }
            if (numIntChild >= 2) interesting = true;
            if (interesting || numIntChild >= 1) hasInterestingInSubtree = true;
        }

        void init() {
            subtreeSize = 1;
            subtreeAnswer = 0;
            childSquareSum = 0;
            boringChildrenSize = 0;
            boringChildrenAnswer = 0;
            boringChildrenSquareSum = 0;
            Vertex v = firstChild;
            while (v != null) {
                v.init();
                subtreeSize += v.subtreeSize;
                subtreeAnswer += v.subtreeAnswer;
                childSquareSum += v.subtreeSize * (long) v.subtreeSize;
                if (interesting && !v.hasInterestingInSubtree) {
                    boringChildrenSize += v.subtreeSize;
                    boringChildrenAnswer += v.subtreeAnswer;
                    boringChildrenSquareSum += v.subtreeSize * (long) v.subtreeSize;
                }
                v = v.nextSibling;
            }
            subtreeAnswer += (subtreeSize * (long) subtreeSize - childSquareSum) * s;
        }

        public void interestingInit() {
            subtreeSize = 1 + boringChildrenSize;
            subtreeAnswer = boringChildrenAnswer;
            childSquareSum = boringChildrenSquareSum;
            Vertex v = firstInterestingChild;
            while (v != null) {
                v.interestingInit();
                long childSize = v.subtreeSize + v.intermediatesSize;
                subtreeSize += childSize;
                subtreeAnswer += v.subtreeAnswer;
                subtreeAnswer += v.multiplierForIntermediates * v.subtreeSize + v.constantForIntermediates;
                childSquareSum += childSize * (long) childSize;
                v = v.nextInterestingSibling;
            }
            subtreeAnswer += (subtreeSize * (long) subtreeSize - childSquareSum) * s;
        }

        public void initIntermediates() {
            Vertex tmp = this;
            intermediatesSize = 0;
            multiplierForIntermediates = 0;
            constantForIntermediates = 0;
            while (!tmp.parent.interesting) {
                long curExtra = tmp.parent.subtreeSize - tmp.subtreeSize;
                intermediatesSize += curExtra;
                multiplierForIntermediates += 2 * curExtra * (long) tmp.parent.s;
                constantForIntermediates += tmp.parent.subtreeAnswer - tmp.subtreeAnswer - 2 * subtreeSize * (long) (tmp.parent.subtreeSize - tmp.subtreeSize) * tmp.parent.s;
                tmp = tmp.parent;
            }
            interestingParent = tmp.parent;
        }
    }

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        /*char[] buf = new char[100000];
        int size;
        try {
            size = in.reader.read(buf);
        } catch (IOException e) {
            throw new RuntimeException(e);
        }
        if (size == buf.length) throw new RuntimeException();
        String input = new String(buf, 0, size);
        StringWriter sw1 = new StringWriter();
        PrintWriter pw1 = new PrintWriter(sw1);
        doit(new InputReader(new StringInputStream(input)), pw1, 1);
        pw1.close();
        StringWriter sw2 = new StringWriter();
        PrintWriter pw2 = new PrintWriter(sw2);
        doit(new InputReader(new StringInputStream(input)), pw2, 500);
        pw2.close();
        String s1 = sw1.toString();
        String s2 = sw2.toString();
        if (!s1.equals(s2)) throw new RuntimeException();
        out.print(s1);*/
        doit(in, out, 500);
    }

    private void doit(InputReader in, PrintWriter out, int BUBEN) {
        Locale.setDefault(Locale.US);
        int n = in.nextInt();
        Vertex[] vs = new Vertex[n];
        for (int i = 0; i < n; ++i) vs[i] = new Vertex();
        for (int i = 1; i < n; ++i) {
            vs[i].parent = vs[in.nextInt() - 1];
        }
        for (int i = 0; i < n; ++i) {
            vs[i].s = in.nextInt();
        }
        Vertex root = vs[0];
        int numQueries = in.nextInt();
        Query[] queries = new Query[numQueries];
        for (int i = 0; i < numQueries; ++i) {
            Query query = new Query();
            String ss = in.next();
            if (ss.equals("P")) query.kind = 1; else if (ss.equals("V")) query.kind = 2; else throw new RuntimeException();
            if (query.kind == 1) {
                query.v = vs[in.nextInt() - 1];
                query.u = vs[in.nextInt() - 1];
            } else {
                query.v = vs[in.nextInt() - 1];
                query.t = in.nextInt();
            }
            queries[i] = query;
        }
        double mult = 1.0 / n / n;
        Vertex[] inters = new Vertex[n];
        for (int blockFirst = 0; blockFirst < numQueries; blockFirst += BUBEN) {
            int blockLast = Math.min(numQueries, blockFirst + BUBEN);
            for (Vertex vv : vs) {
                vv.interesting = false;
                vv.hasInterestingInSubtree = false;
            }
            root.interesting = true;
            for (int qid = blockFirst; qid < blockLast; ++qid) {
                Query query = queries[qid];
                if (query.kind == 1) {
                    query.v.interesting = true;
                    if (query.v.parent != null) query.v.parent.interesting = true;
                    query.u.interesting = true;
                    if (query.u.parent != null) query.u.parent.interesting = true;
                } else {
                    query.v.interesting = true;
                }
            }
            for (Vertex vv : vs) {
                vv.firstChild = null;
                vv.nextSibling = null;
            }
            for (Vertex vv : vs) {
                if (vv.parent != null) {
                    vv.nextSibling = vv.parent.firstChild;
                    vv.parent.firstChild = vv;
                }
            }
            root.propagateInteresting();
            int ninters = 0;
            for (Vertex vv : vs) if (vv.interesting) {
                inters[ninters++] = vv;
            }
            root.init();
            for (int i = 0; i < ninters; ++i) {
                Vertex vv = inters[i];
                if (vv.parent != null) vv.initIntermediates();
            }
            if (blockFirst == 0) {
                out.println(String.format("%.12f", root.subtreeAnswer * mult));
            }
            for (int qid = blockFirst; qid < blockLast; ++qid) {
                Query query = queries[qid];
                if (query.kind == 1) {
                    Vertex tmp = query.u;
                    while (tmp != null && tmp != query.v) tmp = tmp.interestingParent;
                    if (tmp == null) {
                        query.v.parent = query.u;
                        query.v.interestingParent = query.u;
                    } else {
                        query.u.parent = query.v;
                        query.u.interestingParent = query.v;
                    }
                } else {
                    query.v.s = query.t;
                }
                for (int i = 0; i < ninters; ++i) {
                    Vertex vv = inters[i];
                    vv.firstInterestingChild = null;
                    vv.nextInterestingSibling = null;
                }
                for (int i = 0; i < ninters; ++i) {
                    Vertex vv = inters[i];
                    if (vv.interestingParent != null) {
                        vv.nextInterestingSibling = vv.interestingParent.firstInterestingChild;
                        vv.interestingParent.firstInterestingChild = vv;
                    }
                }
                root.interestingInit();
                out.println(String.format("%.12f", root.subtreeAnswer * mult));
            }
        }
    }
}

class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
        reader = new BufferedReader(new InputStreamReader(stream), 32768);
        tokenizer = null;
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

}