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>
template <typename T>
inline void ckmax(T& x, T y) {
  x = (y > x ? y : x);
}
template <typename T>
inline void ckmin(T& x, T y) {
  x = (y < x ? y : x);
}
using namespace std;
const long long inf = 0x7f7f7f7f7f7f7f3f;
const long long mod = 1e9 + 7;
const long double eps = 1e-8;
inline long long fpow(long long a, long long b) {
  long long res = 1;
  while (b) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}
inline long long read() {
  char c = getchar();
  long long x = 0;
  bool f = 0;
  for (; !isdigit(c); c = getchar()) f ^= !(c ^ 45);
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
  if (f) x = -x;
  return x;
}
const long long N = 1e6 + 10;
long long n, q;
long long Ffa[N], a[N], siz[N];
long long res;
vector<long long> e[N];
char opt[111];
struct LinkCutTree {
  long long son[N][2], fa[N], siz[N], sum[N], tag[N], st[N];
  long long susqr[N], siz2[N], wei[N];
  inline long long get(long long x) { return x == son[fa[x]][1]; }
  inline long long isnotroot(long long x) {
    return son[fa[x]][1] == x || son[fa[x]][0] == x;
  }
  inline void push_up(long long x) {
    sum[x] = sum[son[x][0]] + sum[son[x][1]] + 1ll * siz2[x] * wei[x];
    siz[x] = siz[son[x][0]] + siz[son[x][1]] + siz2[x];
  }
  inline void push_add(long long x, long long y) {
    tag[x] += y;
    susqr[x] += (1ll * siz2[x] * y);
  }
  inline void push_down(long long x) {
    if (tag[x]) {
      if (son[x][0]) push_add(son[x][0], tag[x]);
      if (son[x][1]) push_add(son[x][1], tag[x]);
      tag[x] = 0;
    }
  }
  void update(long long x) {
    if (isnotroot(x)) update(fa[x]);
    push_down(x);
  }
  void rotate(long long x) {
    long long f = fa[x], gf = fa[f], wh = get(x);
    if (isnotroot(f)) son[gf][get(f)] = x;
    son[f][wh] = son[x][wh ^ 1];
    fa[son[x][wh ^ 1]] = f;
    son[x][wh ^ 1] = f;
    fa[f] = x, fa[x] = gf;
    push_up(f), push_up(x);
  }
  inline void splay(long long x) {
    update(x);
    for (long long f; f = fa[x], isnotroot(x); rotate(x))
      if (isnotroot(f)) rotate(get(x) == get(f) ? f : x);
    push_up(x);
  }
  inline long long access(long long x) {
    long long y;
    for (y = 0; x; y = x, x = fa[x])
      splay(x), siz2[x] += siz[son[x][1]] - siz[y], son[x][1] = y, push_up(y);
    return y;
  }
  inline long long make_root(long long x) { access(x), splay(x); }
  inline long long find_root(long long x) {
    access(x), splay(x);
    while (son[x][0]) push_down(x), x = son[x][0];
    splay(x);
    return x;
  }
  void dosomething(long long x, long long y) {
    access(x), access(Ffa[x]);
    long long ss = siz[x];
    splay(Ffa[x]);
    siz2[Ffa[x]] -= ss;
    push_up(Ffa[x]);
    res -= (2ll * sum[Ffa[x]] * ss);
    push_add(Ffa[x], -2ll * ss);
    access(y), fa[x] = Ffa[x] = y;
    splay(y);
    res += (2ll * sum[y] * ss);
    push_add(y, 2ll * ss);
    siz2[y] += ss;
    push_up(y);
  }
  void perform(long long x, long long y) {
    if (x == 1)
      dosomething(y, 1);
    else {
      access(x), access(Ffa[x]);
      fa[x] = 0;
      long long ss = siz[x];
      splay(Ffa[x]);
      siz2[Ffa[x]] -= ss;
      push_up(Ffa[x]);
      if (find_root(y) == x) {
        access(Ffa[x]);
        fa[x] = Ffa[x], splay(Ffa[x]);
        siz2[Ffa[x]] += ss, push_up(Ffa[x]);
        dosomething(y, x);
      } else {
        access(Ffa[x]);
        fa[x] = Ffa[x], splay(Ffa[x]);
        siz2[Ffa[x]] += ss, push_up(Ffa[x]);
        dosomething(x, y);
      }
    }
  }
  void upd(long long x, long long y) {
    splay(x), wei[x] += y, push_up(x), res += (1ll * y * susqr[x]);
  }
} LCT;
void dfs(long long u) {
  siz[u] = 1;
  for (long long v : e[u]) {
    dfs(v), siz[u] += siz[v];
  }
}
inline void print() {
  double x = (double)res / (double)n / (double)n;
  printf("%.10lf\n", x);
}
signed main() {
  n = read();
  for (long long i = (2), iE = (n); i <= iE; i++)
    LCT.fa[i] = Ffa[i] = read(), e[Ffa[i]].push_back(i);
  for (long long i = (1), iE = (n); i <= iE; i++) a[i] = read();
  dfs(1);
  for (long long u = (1), uE = (n); u <= uE; u++) {
    res += (1ll * siz[u] * siz[u] * a[u]);
    LCT.susqr[u] += (1ll * siz[u] * siz[u]);
    for (long long v : e[u]) {
      res -= (1ll * siz[v] * siz[v] * a[u]);
      LCT.susqr[u] -= (1ll * siz[v] * siz[v]);
    }
  }
  for (long long i = (1), iE = (n); i <= iE; i++) {
    LCT.siz2[i] = LCT.siz[i] = siz[i];
    LCT.wei[i] = a[i];
    LCT.sum[i] = siz[i] * a[i];
  }
  print();
  q = read();
  for (long long i = (1), iE = (q); i <= iE; i++) {
    scanf("%s", opt + 1);
    long long u = read(), v = read();
    if (opt[1] == 'P') LCT.perform(u, v);
    if (opt[1] == 'V') LCT.upd(u, v - a[u]), a[u] = v;
    print();
  }
}