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 INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 50007;
int n;
int a[MAXN];
int p[MAXN];
long long ans;
class lctT {
 public:
  void link(int u, int v) {
    croot(u);
    access(v);
    fa[u] = v;
    sv[v] += sa[u];
    sv2[v] += (static_cast<long long>(sa[u]) * (sa[u]));
    access(u);
  }
  void cut(int u, int v) {
    croot(u);
    access(v);
    access(u);
    fa[v] = 0;
    sv[u] -= sa[v];
    sv2[u] -= (static_cast<long long>(sa[v]) * (sa[v]));
    upd(u);
  }
  void upd1(int u, int v) {
    if (insubtree(u, v)) {
      upd1(v, u);
      return;
    }
    int nf = p[u];
    cut(u, nf);
    croot(1);
    croot(u);
    access(u);
    int us = sa[u];
    access(nf);
    ans -= 2 * data[nf] * us;
    access(v);
    ans += 2 * data[v] * us;
    link(u, v);
    p[u] = v;
  }
  void upd2(int u, int x) {
    croot(1);
    access(u);
    if (p[u]) access(p[u]);
    ans += (x - a[u]) * ((static_cast<long long>(sa[u]) * (sa[u])) - sv2[u]);
    a[u] = x;
  }

 private:
  void rot(int now) {
    int nf = fa[now], np = fa[nf], d = ch[nf][1] == now;
    fa[now] = np;
    if (!isroot(nf)) ch[np][ch[np][1] == nf] = now;
    fa[ch[now][d ^ 1]] = nf, ch[nf][d] = ch[now][d ^ 1];
    fa[nf] = now, ch[now][d ^ 1] = nf;
    upd(nf), upd(now);
  }
  void splay(int now) {
    rev_push(now);
    int nf, np;
    while (!isroot(now)) {
      nf = fa[now], np = fa[nf];
      if (!isroot(nf))
        rot(((ch[nf][0] == now) == (ch[np][0] == nf)) ? nf : now);
      rot(now);
    }
  }
  void access(int now) {
    int v = 0, tn = now;
    while (now) {
      splay(now);
      sv[now] += sa[ch[now][1]];
      sv2[now] += (static_cast<long long>(sa[ch[now][1]]) * (sa[ch[now][1]]));
      ch[now][1] = v;
      sv[now] -= sa[ch[now][1]];
      sv2[now] -= (static_cast<long long>(sa[ch[now][1]]) * (sa[ch[now][1]]));
      upd(now);
      v = now, now = fa[now];
    }
    splay(tn);
  }
  void croot(int now) {
    access(now);
    rev[now] = true;
  }
  bool insubtree(int u, int v) {
    croot(1);
    access(v);
    return getrt(u) == 1;
  }
  int getrt(int now) {
    while (!isroot(now)) now = fa[now];
    while (ch[now][0]) now = ch[now][0];
    splay(now);
    return now;
  }
  bool isroot(int now) {
    return (!(fa[now] && ((ch[fa[now]][0] == now) || (ch[fa[now]][1] == now))));
  }
  void push_down(int now) {
    if (rev[now]) {
      rev[ch[now][0]] ^= 1, rev[ch[now][1]] ^= 1;
      swap(ch[now][0], ch[now][1]);
      rev[now] = false;
    }
  }
  void rev_push(int now) {
    if (!isroot(now)) rev_push(fa[now]);
    push_down(now);
  }
  void upd(int now) {
    sa[now] = sv[now] + sa[ch[now][0]] + sa[ch[now][1]] + 1;
    data[now] = data[ch[now][0]] + data[ch[now][1]] +
                static_cast<long long>(a[now]) * (sv[now] + 1);
  }
  bool rev[MAXN];
  int ch[MAXN][2], fa[MAXN];
  int size[MAXN], sv[MAXN], sa[MAXN];
  long long s2[MAXN], sv2[MAXN], data[MAXN];
} lct;
int q;
char qtp[5];
int qa, qb;
int ia[MAXN];
void init();
void input();
void inputq();
void work();
int main() {
  init();
  input();
  work();
}
void init() { ios::sync_with_stdio(false); }
void input() {
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) scanf("%d", &p[i]);
  for (int i = 1; i <= n; ++i) scanf("%d", &ia[i]);
  scanf("%d", &q);
}
void inputq() { scanf("%s%d%d", qtp, &qa, &qb); }
void work() {
  for (int i = 2; i <= n; ++i) lct.link(p[i], i);
  for (int i = 1; i <= n; ++i) lct.upd2(i, ia[i]);
  long long n2 = static_cast<long long>(n) * n;
  printf("%.13lf\n", static_cast<double>(ans) / n2);
  for (int _q = 0; _q < q; ++_q) {
    inputq();
    if (qtp[0] == 'P')
      lct.upd1(qa, qb);
    else
      lct.upd2(qa, qb);
    printf("%.13lf\n", static_cast<double>(ans) / n2);
  }
}