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 MAXN = 5e4 + 5;
long long tot = 0, stree[MAXN], rmost[MAXN], lmost[MAXN], sum1[MAXN],
          sum2[MAXN], lazy[MAXN], s[MAXN], diff[MAXN];
vector<int> graph[MAXN];
unordered_map<int, long long> nums[MAXN];
int p[MAXN], ch[MAXN][2], f[MAXN];
int n, q;
int inv[MAXN];
void dfs(int v, int f1) {
  stree[v] = 1, rmost[v] = lmost[v] = v, p[v] = f[v] = f1,
  ch[v][0] = ch[v][1] = lazy[v] = diff[v] = 0;
  for (int i = 0; i < graph[v].size(); ++i) {
    if (graph[v][i] != f1) {
      dfs(graph[v][i], v);
      stree[v] += stree[graph[v][i]];
      diff[v] -= stree[graph[v][i]] * stree[graph[v][i]];
      nums[v][graph[v][i]] = stree[graph[v][i]];
    }
  }
  sum1[v] = s[v] * stree[v];
  sum2[v] = stree[v] * sum1[v];
  diff[v] += stree[v] * stree[v];
  tot += diff[v] * s[v];
  inv[v] = 0;
}
void upd(int v) {
  rmost[v] = ((ch[v][1] == 0) ? v : rmost[ch[v][1]]);
  long long x = nums[v][rmost[ch[v][0]]];
  lmost[v] = ((ch[v][0] == 0) ? v : lmost[ch[v][0]]);
  if (ch[v][1] != 0) inv[lmost[ch[v][1]]] = v;
  sum1[v] = s[v] * (stree[v] - x) + sum1[ch[v][0]] + sum1[ch[v][1]];
  if (ch[v][1] != 0) sum1[v] -= s[f[v]] * stree[v];
  sum2[v] =
      s[v] * (stree[v] * stree[v] - x * x) + sum2[ch[v][0]] + sum2[ch[v][1]];
  if (ch[v][1] != 0) sum2[v] -= s[f[v]] * stree[v] * stree[v];
}
void mark(int v, int x) {
  if (v == 0) return;
  lazy[v] += x;
  diff[v] += 2 * stree[v] * x + x * x;
  stree[v] += x;
  int y = 0;
  if (ch[v][0] != 0) y = rmost[ch[v][0]];
  if (y == 0) y = inv[v];
  if (y != 0) {
    diff[v] -= 2 * x * nums[v][y] + x * x;
    nums[v][y] += x;
  }
  sum2[v] += 2 * sum1[v] * x;
  sum2[v] += s[lmost[v]] * x * x;
  sum1[v] += s[lmost[v]] * x;
}
void prop(int v) {
  mark(ch[v][0], lazy[v]);
  mark(ch[v][1], lazy[v]);
  lazy[v] = 0;
}
bool isRoot(int v) {
  return (p[v] == 0) || (ch[p[v]][0] != v && ch[p[v]][1] != v);
}
void rot(int v) {
  prop(p[v]);
  prop(v);
  int p1 = p[v];
  bool b = ch[p1][1] == v;
  ch[p1][b] = ch[v][!b], ch[v][!b] = p1;
  if (!isRoot(p1)) ch[p[p1]][ch[p[p1]][1] == p1] = v;
  p[ch[p1][b]] = p1, p[v] = p[p1], p[p1] = v;
  upd(p1);
  upd(v);
}
void splay(int v) {
  while (!isRoot(v)) {
    int p1 = p[v];
    if (!isRoot(p1)) {
      if ((ch[p[p1]][0] == p1) ^ (ch[p1][0] == v))
        rot(v);
      else
        rot(p1);
    }
    rot(v);
  }
}
int expose(int v) {
  int prev = 0;
  for (int m = v; m != 0; m = p[m]) {
    splay(m);
    prop(m);
    ch[m][0] = prev;
    prev = m;
    upd(m);
  }
  splay(v);
  return prev;
}
int lca(int u, int v) {
  expose(u);
  return expose(v);
}
void vchange(int v, int t) {
  expose(v);
  tot += diff[v] * (t - s[v]);
  s[v] = t;
  upd(v);
}
void makeparent(int u, int v) {
  expose(u);
  int d = stree[u];
  expose(v);
  expose(u);
  tot -= d * d * (s[v] - s[f[u]]);
  long long init = sum2[ch[u][1]];
  mark(ch[u][1], -d);
  tot += sum2[ch[u][1]] - init;
  expose(u);
  prop(u);
  expose(ch[u][1]);
  if (ch[u][1] != 0) p[ch[u][1]] = p[u];
  ch[u][0] = ch[u][1] = 0;
  f[u] = p[u] = v;
  expose(u);
  init = sum2[ch[u][1]];
  mark(ch[u][1], d);
  tot += sum2[ch[u][1]] - init;
}
int main() {
  cin >> n;
  sum1[0] = sum2[0] = stree[0] = lazy[0] = diff[0] = 0;
  for (int i = 0; i < n - 1; ++i) {
    int x;
    cin >> x;
    graph[i + 2].push_back(x);
    graph[x].push_back(i + 2);
  }
  for (int i = 0; i < n; ++i) cin >> s[i + 1];
  dfs(1, 0);
  cout << fixed << setprecision(9);
  cout << (double)tot / n / n << endl;
  cin >> q;
  while (q > 0) {
    char x;
    int a, b;
    cin >> x >> a >> b;
    if (x == 'V') {
      vchange(a, b);
    } else {
      if (lca(a, b) != a)
        makeparent(a, b);
      else
        makeparent(b, a);
    }
    cout << (double)tot / n / n << endl;
    q--;
  }
}