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>
using namespace std;
const long long linf = 1e18 + 5;
int mod = (int)1e9 + 7;
const int logN = 18;
const int SQ = 250;
const int inf = 1e9;
const int N = 5e4 + 5;
long long all, ch[N], path[N];
int size[N], ok[N], dp[N], n, m, P[N], p[N], x, y, z, t, val[N], C[N];
vector<pair<int, pair<int, int> > > q;
vector<int> v[N], nodes;
char c;
int up(int x, int y) {
  if (!x) return 0;
  int &r = dp[x];
  if (r != -1) return r;
  if (P[x] == y) return r = x;
  return r = up(P[x], y);
}
int up2(int x) {
  if (ok[x]) return x;
  int &r = dp[x];
  if (r != -1) return r;
  return r = up2(P[x]);
}
int dfs1(int node) {
  size[node] = 1;
  int s = ok[node] ? 2 : 0;
  ch[node] = 0;
  for (__typeof(v[node].begin()) it = v[node].begin(); it != v[node].end();
       it++) {
    s += dfs1(*it);
    size[node] += size[*it];
    ch[node] -= size[*it] * (long long)size[*it];
  }
  ch[node] += size[node] * (long long)size[node];
  if (s >= 2) ok[node] = 1;
  all += ch[node] * (long long)val[node];
  return s != 0;
}
void dfs2(int node, int last, int root, int bef = 0) {
  path[node] = path[root] + (size[root] - size[node]) * (long long)val[root];
  C[node] = size[bef];
  if (ok[node]) {
    nodes.push_back(node);
    P[node] = last;
    last = node;
    bef = -1;
  }
  for (__typeof(v[node].begin()) it = v[node].begin(); it != v[node].end();
       it++) {
    if (bef == -1)
      dfs2(*it, node, node, *it);
    else
      dfs2(*it, last, node, bef);
  }
}
int ctr(int x, int y) {
  while (x) {
    if (x == y) return 1;
    x = P[x];
  }
  return 0;
}
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) scanf("%d", &p[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf(" %c %d %d", &c, &y, &z);
    if (c == 'P') {
      ok[y] = ok[z] = 1;
      q.push_back(make_pair(0, make_pair(y, z)));
    }
    if (c == 'V') {
      ok[y] = 1;
      q.push_back(make_pair(1, make_pair(y, z)));
    }
    if (i == m || i % SQ == 0) {
      for (int i = 1; i <= n; i++) v[i].clear();
      for (int i = 2; i <= n; i++) v[p[i]].push_back(i);
      nodes.clear();
      ok[1] = 1;
      all = 0;
      dfs1(1), dfs2(1, 0, 0, 1);
      memset(ok, 0, sizeof ok);
      for (__typeof(q.begin()) it = q.begin(); it != q.end(); it++) {
        printf("%.12lf\n", all / (1.0 * n * n));
        for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
             it3++)
          ok[*it3] = 0;
        if (it->first == 1) {
          int node = it->second.first, val = it->second.second - ::val[node];
          all += val * ch[it->second.first];
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++)
            dp[*it3] = -1;
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++) {
            int take = up(*it3, node);
            if (take == 0) continue;
            path[*it3] += val * (long long)(size[node] - C[take]);
          }
          ::val[node] += val;
        } else {
          if (ctr(it->second.second, it->second.first))
            swap(it->second.second, it->second.first);
          p[it->second.first] = it->second.second;
          int node = it->second.first, par = P[it->second.first],
              sz = size[node];
          all -= 2 * sz * path[node];
          while (par) {
            ok[par] = ok[node] = 1;
            ch[par] -= 2LL * sz * (size[par] - C[node]);
            size[par] -= sz;
            C[node] -= sz;
            node = P[node];
            par = P[par];
          }
          C[1] -= sz;
          C[it->second.first] = sz;
          long long ggg = path[it->second.first];
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++)
            dp[*it3] = -1;
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++) {
            if (!ok[*it3] || *it3 == it->second.first) {
              int take = up2(*it3);
              if (take == it->second.first)
                path[*it3] -= ggg;
              else
                path[*it3] -= val[take] * (long long)sz;
            }
          }
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++)
            dp[*it3] = -1, ok[*it3] = 0;
          C[it->second.first] = 0;
          node = it->second.first, par = it->second.second, P[node] = par;
          while (par) {
            ok[par] = ok[node] = 1;
            size[par] += sz;
            C[node] += sz;
            ch[par] += 2LL * sz * (size[par] - C[node]);
            node = P[node];
            par = P[par];
          }
          C[1] += sz;
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++)
            dp[*it3] = -1;
          ggg = path[it->second.second] +
                (long long)(size[it->second.second] - sz) *
                    val[it->second.second];
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++) {
            if (!ok[*it3] || *it3 == it->second.first) {
              int take = up2(*it3);
              if (take == it->second.first)
                path[*it3] += ggg;
              else
                path[*it3] += val[take] * (long long)sz;
            }
          }
          all += 2 * path[it->second.first] * size[it->second.first];
          for (__typeof(nodes.begin()) it3 = nodes.begin(); it3 != nodes.end();
               it3++)
            dp[*it3] = -1, ok[*it3] = 0;
        }
      }
      q.clear();
      memset(ok, 0, sizeof ok);
    }
  }
  printf("%.12lf\n", all / (1.0 * n * n));
  return 0;
}