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;
#pragma comment(linker, "/STACK:1024000000,1024000000")
long long ans;
int son[100010][2], fa[100010], cnt[100010], val[100010];
int is[100010];
long long sumVal[100010], sumCnt[100010], sum[100010], all[100010],
    lazy[100010];
void up(int p) {
  sumCnt[p] = sumCnt[son[p][0]] + sumCnt[son[p][1]] + cnt[p];
  sumVal[p] = sumVal[son[p][0]] + sumVal[son[p][1]] + val[p];
  sum[p] = sum[son[p][0]] + sum[son[p][1]] + 1LL * cnt[p] * val[p];
}
void func(int p, long long v) {
  if (!p) return;
  all[p] += v * cnt[p];
  lazy[p] += v;
}
void down(int p) {
  if (lazy[p]) {
    func(son[p][0], lazy[p]);
    func(son[p][1], lazy[p]);
    lazy[p] = 0;
  }
}
void Rotate(int x) {
  int y = fa[x], z = fa[y];
  int o = son[y][0] == x;
  down(y), down(x);
  son[y][!o] = son[x][o], fa[son[x][o]] = y;
  son[x][o] = y, fa[y] = x;
  fa[x] = z;
  if (is[y])
    is[y] = 0, is[x] = 1;
  else
    son[z][son[z][1] == y] = x;
  up(y);
}
void Splay(int x) {
  int y, z;
  down(x);
  while (!is[x]) {
    y = fa[x], z = fa[y];
    if (is[y])
      Rotate(x);
    else if ((son[y][0] == x) ^ (son[z][0] == y))
      Rotate(x), Rotate(x);
    else
      Rotate(y), Rotate(x);
  }
  up(x);
}
int Access(int x) {
  int y = 0;
  for (; x; x = fa[x]) {
    Splay(x);
    is[son[x][1]] = 1;
    if (son[x][1]) {
      cnt[x] += sumCnt[son[x][1]];
    }
    son[x][1] = y;
    if (y) {
      cnt[x] -= sumCnt[y];
    }
    is[y] = 0;
    y = x;
    up(x);
  }
  return y;
}
int vv[100010], nxt[100010], h[100010], e;
void add(int u, int v) { vv[e] = v, nxt[e] = h[u], h[u] = e++; }
void dfs(int u, int f) {
  fa[u] = f, is[u] = 1, cnt[u] = 1;
  son[u][0] = son[u][1] = 0;
  all[u] = 1;
  for (int i = h[u]; i + 1; i = nxt[i]) {
    int v = vv[i];
    dfs(v, u);
    all[u] += 1LL * cnt[v] * cnt[u] * 2;
    cnt[u] += cnt[v];
  }
  ans += all[u] * val[u];
  up(u);
}
void change(int x, long long v) {
  Splay(x);
  ans += (v - val[x]) * all[x];
  val[x] = v;
  up(x);
}
int getFa(int x) {
  Splay(x);
  if (!son[x][0]) return fa[x];
  int y = son[x][0];
  while (son[y][1]) y = son[y][1];
  return y;
}
void gao(int u, int v) {
  Access(u);
  Splay(v);
  if (!fa[v]) swap(u, v);
  int f = getFa(v);
  if (f == u) return;
  Access(f), Splay(f);
  cnt[f] -= sumCnt[v], up(f);
  fa[v] = 0;
  ans -= 2 * sum[f] * sumCnt[v];
  func(f, -2 * sumCnt[v]);
  Access(u), Splay(u);
  ans += 2 * sum[u] * sumCnt[v];
  func(u, 2 * sumCnt[v]);
  cnt[u] += sumCnt[v], up(u);
  fa[v] = u;
}
int main() {
  int n;
  int u;
  scanf("%d", &n);
  memset(h, -1, sizeof(h)), e = 0;
  for (int i = 2; i <= n; ++i) {
    scanf("%d", &u);
    add(u, i);
  }
  for (int i = 1; i <= n; ++i) scanf("%d", val + i);
  dfs(1, 0);
  int m, v;
  scanf("%d", &m);
  char c[3];
  double mu = 1.0 * n * n;
  printf("%.10lf\n", ans / mu);
  while (m--) {
    scanf("%s%d%d", c, &u, &v);
    if (c[0] == 'P')
      gao(v, u);
    else
      change(u, v);
    printf("%.10lf\n", ans / mu);
  }
}