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 int N = 5e4 + 5;
const int K = 250;
int n, m;
int X[N], Y[N];
char C[N];
vector<int> v[N];
int imp[N], down[N], up[N], par[N], dep[N];
long long ans;
long long sub[N], coef[N], coefUp[N], s[N];
void dfs(int x) {
  sub[x] = 1;
  down[x] = 0;
  coef[x] = 0;
  coefUp[x] = 0;
  int come = 0;
  for (auto u : v[x]) {
    dep[u] = dep[x] + 1;
    dfs(u);
    if (down[u]) {
      if (down[x]) imp[x] = 1;
      down[x] = down[u];
      come = u;
    }
    sub[x] += sub[u];
    coef[x] -= sub[u] * sub[u];
  }
  coef[x] += sub[x] * sub[x];
  ans += coef[x] * s[x];
  up[x] = x;
  if (imp[x]) {
    down[x] = x;
  } else {
    coefUp[down[x]] += (sub[x] - sub[come]) * s[x];
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) {
    scanf("%d", par + i);
    v[par[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) scanf("%lld", s + i);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    scanf(" %c %d %d", C + i, X + i, Y + i);
  }
  for (int it = 1; it <= m; it += K) {
    int end = min(m, it + K - 1);
    memset(imp, 0, sizeof(imp));
    for (int i = it; i <= end; i++) {
      imp[X[i]] = 1;
      if (C[i] == 'P') imp[Y[i]] = 1;
    }
    ans = 0;
    dfs(1);
    for (int i = 1; i <= n; i++) {
      if (down[i] and dep[i] < dep[up[down[i]]]) up[down[i]] = i;
    }
    for (int i = it; i <= end; i++) {
      printf("%.12lf\n", (double)ans / n / n);
      int c = C[i], x = X[i], y = Y[i];
      if (c == 'P') {
        int u = y;
        while (u and u != x) {
          u = par[up[u]];
        }
        if (u == x) swap(x, y);
        u = x;
        for (;;) {
          ans -= 2 * coefUp[u] * sub[x];
          int v = par[up[u]];
          if (!v) break;
          ans -= coef[v] * s[v];
          if (up[u] != u) {
            sub[v] -= sub[x];
            sub[up[u]] -= sub[x];
            coef[v] -= 2 * (sub[v] - sub[up[u]]) * sub[x];
          } else if (u != x) {
            sub[v] -= sub[x];
            coef[v] -= 2 * (sub[v] - sub[up[u]]) * sub[x];
          } else {
            coef[v] -= 2 * (sub[v] - sub[up[u]]) * sub[x];
            sub[v] -= sub[x];
          }
          ans += coef[v] * s[v];
          u = v;
        }
        u = y;
        for (;;) {
          ans += 2 * coefUp[u] * sub[x];
          int v = par[up[u]];
          if (!v) break;
          ans -= coef[v] * s[v];
          if (up[u] != u) {
            sub[v] += sub[x];
            sub[up[u]] += sub[x];
            coef[v] += 2 * (sub[v] - sub[up[u]]) * sub[x];
          } else if (u != y) {
            sub[v] += sub[x];
            coef[v] += 2 * (sub[v] - sub[up[u]]) * sub[x];
          } else {
            coef[v] += 2 * (sub[v] - sub[up[u]]) * sub[x];
            sub[v] += sub[x];
          }
          ans += coef[v] * s[v];
          u = v;
        }
        ans -= coef[y] * s[y];
        coef[y] += 2 * sub[y] * sub[x];
        sub[y] += sub[x];
        ans += coef[y] * s[y];
        up[x] = x;
        par[x] = y;
        coefUp[x] = 0;
      } else {
        ans -= coef[x] * s[x];
        s[x] = y;
        ans += coef[x] * s[x];
      }
    }
    for (int i = 1; i <= n; i++) v[i].clear();
    for (int i = 2; i <= n; i++) v[par[i]].push_back(i);
  }
  printf("%.12lf\n", (double)ans / n / n);
  return 0;
}