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 CPP):

Solution:
#include <bits/stdc++.h>
const int K = 223;
const int MAXK = 8 * K;
double H;
bool first;
long long ans;
int n, k, rad, alfa;
int t[50000 + 1], l[50000 + 1], r[50000 + 1], g[50000 + 1];
int s[50000 + 1], v[50000 + 1], cine[MAXK], cat[MAXK];
int S[MAXK], V[MAXK], ind[50000 + 1], T[MAXK];
int R[MAXK], L[MAXK], G[MAXK], baza[MAXK];
int node1[MAXK], node2[MAXK];
long long d[50000 + 1], D[MAXK], add[MAXK], per[MAXK];
char viz[50000 + 1], tip[MAXK];
void dfs1(int x) {
  s[x] = 1;
  for (int i = l[x]; i < r[x]; i++) {
    dfs1(g[i]);
    s[x] += s[g[i]];
    viz[x] += bool(viz[g[i]]);
  }
}
void dfs2(int x) {
  d[x] = d[t[x]] + 1LL * v[t[x]] * (s[t[x]] - s[x]);
  if (first) ans += d[x] + 1LL * s[x] * v[x];
  ind[x] = 0;
  int cnt = 1;
  long long perechi = 1;
  for (int i = l[x]; i < r[x]; i++) {
    dfs2(g[i]);
    if (viz[g[i]] == 1 && viz[x] == 1) {
      int e = ind[x] = ind[g[i]];
      add[e] += 1LL * v[x] * (s[x] - s[g[i]]);
      cat[e] = s[x] - S[e];
      cine[e] = x;
    }
    if (viz[g[i]] == 0) {
      perechi += 2LL * s[g[i]] * cnt;
      cnt += s[g[i]];
    }
  }
  if (viz[x] && ind[x] == 0) {
    ind[x] = ++k;
    cine[k] = x;
    per[k] = perechi;
    baza[k] = cnt;
    cat[k] = add[k] = 0;
    V[k] = v[x];
    S[k] = s[x];
    D[k] = d[x];
  }
}
void dfs3(int x) {
  S[x] = baza[x];
  for (int i = L[x]; i < R[x]; i++) {
    dfs3(G[i]);
    S[x] += S[G[i]] + cat[G[i]];
  }
}
void dfs4(int x) {
  D[x] = D[T[x]] + add[x] + 1LL * V[T[x]] * (S[T[x]] - (S[x] + cat[x]));
  for (int i = L[x]; i < R[x]; i++) dfs4(G[i]);
}
void dfs5(int x) {
  ans += alfa * D[x] * (baza[x] + cat[x]);
  for (int i = L[x]; i < R[x]; i++) dfs5(G[i]);
}
inline void graf() {
  memset(R, 0, sizeof R);
  for (int i = 1; i <= k; i++)
    if (T[i]) R[T[i]]++;
  for (int i = 1; i <= k; i++) {
    R[i] += R[i - 1];
    L[i] = R[i];
  }
  for (int i = 1; i <= k; i++)
    if (T[i]) G[--L[T[i]]] = i;
  dfs3(rad);
}
inline void go(int a, int b) {
  t[a] = b;
  a = ind[a];
  b = ind[b];
  alfa = -2;
  dfs5(a);
  T[a] = b;
  graf();
  dfs4(rad);
  alfa = 2;
  dfs5(a);
}
inline void change(int a, int w) {
  v[a] = w;
  a = ind[a];
  int cnt = baza[a];
  long long perechi = per[a];
  for (int i = L[a]; i < R[a]; i++) {
    perechi += 2LL * (S[G[i]] + cat[G[i]]) * cnt;
    cnt += S[G[i]] + cat[G[i]];
  }
  ans += (w - V[a]) * perechi;
  V[a] = w;
  dfs4(a);
}
inline void solve(int u) {
  memset(r, 0, sizeof r);
  for (int i = 2; i <= n; i++) r[t[i]]++;
  for (int i = 1; i <= n; i++) {
    r[i] += r[i - 1];
    l[i] = r[i];
  }
  for (int i = 2; i <= n; i++) g[--l[t[i]]] = i;
  memset(viz, 0, sizeof viz);
  for (int i = 0; i < u; i++)
    if (tip[i] == 'P')
      viz[node1[i]] = viz[node2[i]] = 2;
    else
      viz[node1[i]] = 2;
  dfs1(1);
  k = 0;
  dfs2(1);
  rad = ind[1];
  for (int i = 1; i <= k; i++) T[i] = ind[t[cine[i]]];
  graf();
  for (int i = 0; i < u; i++) {
    fprintf(stdout, "%.15f\n", ans / H);
    first = 0;
    if (tip[i] == 'P') {
      int a = ind[node1[i]], b = ind[node2[i]];
      int x = b;
      while (x != a && x != rad) x = T[x];
      if (x == a)
        go(node2[i], node1[i]);
      else
        go(node1[i], node2[i]);
    } else
      change(node1[i], node2[i]);
  }
}
int main() {
  fscanf(stdin, "%d", &n);
  H = 1LL * n * n;
  for (int i = 2; i <= n; i++) fscanf(stdin, "%d", &t[i]);
  for (int i = 1; i <= n; i++) fscanf(stdin, "%d", &v[i]);
  int q;
  fscanf(stdin, "%d ", &q);
  int u = 0;
  first = 1;
  for (; q; q--) {
    fscanf(stdin, "%c%d%d ", &tip[u], &node1[u], &node2[u]);
    u++;
    if (u == K) {
      solve(u);
      u = 0;
    }
  }
  if (u != 0) solve(u);
  fprintf(stdout, "%.15f\n", ans / H);
  fclose(stdin);
  fclose(stdout);
  return 0;
}