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;
inline long long read() {
  long long x = 0, neg = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
  return x * neg;
}
inline void print(long long x) {
  if (x < 0) {
    putchar('-');
    print(abs(x));
    return;
  }
  if (x <= 9)
    putchar(x + '0');
  else {
    print(x / 10);
    putchar(x % 10 + '0');
  }
}
inline long long qpow(long long x, long long e, long long _MOD) {
  long long ans = 1;
  while (e) {
    if (e & 1) ans = ans * x % _MOD;
    x = x * x % _MOD;
    e >>= 1;
  }
  return ans;
}
long long n = read(), a[100005];
struct node {
  long long f, ch[2];
  long long sz_im, sz_im_sqr, sz;
  long long ans, ans_im, ans_re;
} s[100005];
inline void pushup(long long k) {
  s[k].sz = s[s[k].ch[0]].sz + s[s[k].ch[1]].sz + s[k].sz_im;
  s[k].ans_re = s[s[k].ch[0]].ans_re + s[s[k].ch[1]].ans_re + s[k].sz_im * a[k];
  s[k].ans = 0;
  s[k].ans += s[s[k].ch[0]].ans + s[s[k].ch[1]].ans;
  s[k].ans += s[k].ans_im;
  s[k].ans += (s[k].sz_im * s[k].sz_im - s[k].sz_im_sqr) * a[k];
  s[k].ans += s[k].sz_im * s[s[k].ch[1]].sz * a[k] * 2;
  s[k].ans += s[s[k].ch[0]].ans_re * (s[k].sz - s[s[k].ch[0]].sz) * 2;
}
inline long long identify(long long k) {
  if (s[s[k].f].ch[0] == k) return 0;
  if (s[s[k].f].ch[1] == k) return 1;
  return -1;
}
inline void connect(long long k, long long f, long long op) {
  s[k].f = f;
  if (op == -1) return;
  s[f].ch[op] = k;
}
inline void rotate(long long x) {
  long long y = s[x].f;
  long long z = s[y].f;
  long long opx = identify(x);
  long long opy = identify(y);
  long long u = 0;
  if (opx == 1) u = s[x].ch[0];
  if (opx == 0) u = s[x].ch[1];
  connect(u, y, opx);
  connect(y, x, opx ^ 1);
  connect(x, z, opy);
  pushup(y);
  pushup(x);
}
inline void splay(long long x) {
  while (identify(x) != -1) {
    long long up = s[x].f;
    if (identify(up) == -1)
      rotate(x);
    else if (identify(up) == identify(x))
      rotate(up), rotate(x);
    else
      rotate(x), rotate(x);
  }
}
inline void access(long long x) {
  long long y = 0;
  while (x) {
    splay(x);
    s[x].sz_im += s[s[x].ch[1]].sz;
    s[x].sz_im_sqr += s[s[x].ch[1]].sz * s[s[x].ch[1]].sz;
    s[x].ans_im += s[s[x].ch[1]].ans;
    s[x].ch[1] = y;
    s[x].sz_im -= s[s[x].ch[1]].sz;
    s[x].sz_im_sqr -= s[s[x].ch[1]].sz * s[s[x].ch[1]].sz;
    s[x].ans_im -= s[s[x].ch[1]].ans;
    pushup(x);
    y = x;
    x = s[x].f;
  }
}
inline void link(long long x, long long y) {
  access(x);
  splay(x);
  access(y);
  splay(y);
  s[x].f = y;
  s[y].ans_im += s[x].ans;
  s[y].sz_im += s[x].sz;
  s[y].sz_im_sqr += s[x].sz * s[x].sz;
  pushup(y);
}
inline void cut(long long x, long long y) {
  access(y);
  splay(y);
  splay(x);
  s[y].ans_im -= s[x].ans;
  s[y].sz_im -= s[x].sz;
  s[y].sz_im_sqr -= s[x].sz * s[x].sz;
  s[x].f = 0;
  pushup(y);
}
inline bool anc(long long x, long long y) {
  access(y);
  splay(y);
  splay(x);
  if (identify(y) != -1)
    return 1;
  else
    return 0;
}
long long fa[100005];
signed main() {
  for (long long i = 2; i <= n; i++) fa[i] = read();
  for (long long i = 1; i <= n; i++) a[i] = read();
  for (long long i = 1; i <= n; i++)
    s[i].ans = s[i].ans_re = a[i], s[i].sz_im = s[i].sz = 1;
  for (long long i = 2; i <= n; i++) link(i, fa[i]);
  access(1);
  splay(1);
  printf("%.10lf\n", 1. * s[1].ans / n / n);
  long long T = read();
  while (T--) {
    char opt[15];
    scanf("%s", opt + 1);
    if (opt[1] == 'P') {
      long long x = read(), y = read();
      if (anc(x, y)) {
        if (fa[y]) cut(y, fa[y]);
        fa[y] = x;
        link(y, fa[y]);
      } else {
        if (fa[x]) cut(x, fa[x]);
        fa[x] = y;
        if (fa[x]) link(x, fa[x]);
      }
      access(1);
      splay(1);
      printf("%.10lf\n", 1. * s[1].ans / n / n);
    } else {
      long long x = read(), y = read();
      access(x);
      splay(x);
      a[x] = y;
      pushup(x);
      access(x);
      splay(x);
      printf("%.10lf\n", 1. * s[x].ans / n / n);
    }
  }
  return 0;
}