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 Imx = 2147483647;
const long long Lbig = 2e18;
const int mod = 1e9 + 7;
struct fastio {
  char s[100000];
  int it, len;
  fastio() { it = len = 0; }
  inline char get() {
    if (it < len) return s[it++];
    it = 0;
    len = fread(s, 1, 100000, stdin);
    if (len == 0)
      return EOF;
    else
      return s[it++];
  }
  bool notend() {
    char c = get();
    while (c == ' ' || c == '\n') c = get();
    if (it > 0) it--;
    return c != EOF;
  }
} _buff;
inline long long getnum() {
  long long r = 0;
  bool ng = 0;
  char c;
  c = _buff.get();
  while (c != '-' && (c < '0' || c > '9')) c = _buff.get();
  if (c == '-') ng = 1, c = _buff.get();
  while (c >= '0' && c <= '9') r = r * 10 + c - '0', c = _buff.get();
  return ng ? -r : r;
}
template <class T>
inline void putnum(T x) {
  if (x < 0) putchar('-'), x = -x;
  register short a[20] = {}, sz = 0;
  while (x) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
}
inline char getreal() {
  char c = _buff.get();
  while (c <= 32) c = _buff.get();
  return c;
}
int n;
struct node {
  int fa, go[2];
  long long val, lzv, s, d, all;
  long long ssd;
  node() { fa = go[0] = go[1] = val = lzv = s = d = all = ssd = 0; }
  void addval(long long v) {
    all += 2 * v * d;
    lzv += v;
    val += v;
  }
} a[200111];
void pushdown(int p) {
  long long &lzv = a[p].lzv;
  if (lzv) {
    if (a[p].go[0]) a[a[p].go[0]].addval(lzv);
    if (a[p].go[1]) a[a[p].go[1]].addval(lzv);
    lzv = 0;
  }
}
void update(int p) {
  a[p].ssd = a[p].s * a[p].d + a[a[p].go[0]].ssd + a[a[p].go[1]].ssd;
}
int getdir(int p) {
  return a[a[p].fa].go[0] == p ? 0 : (a[a[p].fa].go[1] == p ? 1 : -1);
}
void rotate(int p, bool d) {
  int q = a[p].go[d];
  int r = a[q].go[d ^ 1];
  if (getdir(p) != -1) a[a[p].fa].go[getdir(p)] = q;
  a[q].go[d ^ 1] = p;
  a[p].go[d] = r;
  a[q].fa = a[p].fa;
  a[p].fa = q;
  if (r) a[r].fa = p;
  update(p);
}
void pushroute(int p) {
  if (getdir(p) != -1) pushroute(a[p].fa);
  pushdown(p);
}
void debug() {
  for (int p = 0; p <= n; p++) {
    cerr << p << ":" << a[p].go[0] << "," << a[p].go[1] << " " << a[p].fa
         << " val=" << a[p].val << " s=" << a[p].s << " d=" << a[p].d << " "
         << a[p].all << " ssd=" << a[p].ssd << endl;
  }
}
void splay(int p, int t = -1) {
  pushroute(p);
  while (getdir(p) != -1 && a[p].fa != t) {
    int q = a[p].fa, r = a[q].fa;
    int dq = getdir(p), dr = getdir(q);
    if (dr == -1 || r == t)
      rotate(q, dq);
    else {
      if (dq == dr)
        rotate(r, dr), rotate(q, dq);
      else
        rotate(q, dq), rotate(r, dr);
    }
  }
  update(p);
}
int leftmost(int p) {
  assert(a[p].go[0] >= 0);
  return a[p].go[0] > 0 ? leftmost(a[p].go[0]) : p;
}
int access(int p) {
  assert(p > 0);
  int ret = p;
  for (splay(p), a[p].go[1] = 0, a[p].d = a[p].val; a[p].fa; splay(p)) {
    splay(a[p].fa);
    int fa = a[p].fa, lm = leftmost(p);
    splay(lm);
    a[fa].d = a[fa].val - a[lm].val;
    splay(p);
    assert(a[p].fa > 0);
    a[a[p].fa].go[1] = p;
    update(a[p].fa);
    ret = a[p].fa;
  }
  return ret;
}
long long curans;
void subtree_addval(int p, long long v) {
  curans += 2 * a[p].ssd * v;
  a[p].addval(v);
}
void node_adds(int p, long long v) {
  access(p);
  curans += v * a[p].all;
  a[p].s += v;
  update(p);
}
void cut(int x, int p) {
  access(x);
  splay(p);
  a[p].d = a[p].val - a[x].val;
  assert(a[x].fa == p);
  a[p].go[1] = 0;
  a[x].fa = 0;
  update(p);
  subtree_addval(p, -a[x].val);
}
void link(int x, int p) {
  access(p);
  access(x);
  a[x].fa = p;
  a[p].d = a[p].val;
  update(p);
  subtree_addval(p, a[x].val);
}
int getlca(int x, int y) {
  access(x);
  return access(y);
}
int q, p[100111], s[100111];
int main() {
  n = getnum();
  for (int i = 2; i <= n; i++) p[i] = getnum();
  for (int i = 1; i <= n; i++) s[i] = getnum();
  for (int i = 1; i <= n; i++) {
    node_adds(i, s[i]);
    curans += s[i];
    a[i].val = a[i].d = a[i].all = 1;
    splay(i);
  }
  for (int i = 2; i <= n; i++) {
    link(i, p[i]);
  }
  q = getnum();
  printf("%.10lf\n", 1.0 * curans / n / n);
  for (int _ = 1; _ <= q; _++) {
    char op = getreal();
    int x, y;
    x = getnum(), y = getnum();
    if (op == 'P') {
      int lca = getlca(x, y);
      if (x == lca) swap(x, y);
      cut(x, p[x]);
      p[x] = y;
      link(x, p[x]);
    } else {
      node_adds(x, y - s[x]);
      s[x] = y;
    }
    printf("%.10lf\n", 1.0 * curans / n / n);
  }
  return 0;
}