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>
void read(T &x);
template <typename T>
void read(T &x, T &y);
template <typename T>
void read(T &x, T &y, T &z);
template <typename T>
void write(T x);
template <typename T>
void writeC(T x);
template <typename T>
void writeN(T x);
long long size[100005], psum[100005], ans[100005], star[100005], Vans[100005],
    Vdet[100005], w[100005];
int n, fa[100005], p[100005], ch[100005][2], q, u, v, x, y;
char s[10];
int not_root(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; }
void update(int x) {
  size[x] = size[ch[x][0]] + size[ch[x][1]] + star[x];
  psum[x] = psum[ch[x][0]] + psum[ch[x][1]] + (long long)w[x] * star[x];
  ans[x] = Vans[x] + ans[ch[x][0]] + ans[ch[x][1]] +
           (long long)w[x] * (star[x] * star[x] - Vdet[x]) +
           2ll * w[x] * star[x] * size[ch[x][1]] +
           2ll * psum[ch[x][0]] * (size[x] - size[ch[x][0]]);
}
void rotate(int x) {
  int f = fa[x], g = fa[f], l = ch[f][1] == x, l2 = ch[g][1] == f,
      c = ch[x][l ^ 1];
  if (not_root(f)) ch[g][l2] = x;
  ch[f][l] = c;
  ch[x][l ^ 1] = f;
  fa[x] = g;
  fa[f] = x;
  if (c) fa[c] = f;
  update(f);
  update(x);
}
void splay(int x) {
  while (not_root(x)) {
    if (not_root(fa[x]))
      rotate(rand() % 2 ? fa[x] : x);
    else
      rotate(x);
  }
}
void access(int x) {
  for (int y = 0; x; x = fa[y = x]) {
    splay(x);
    int z = ch[x][1];
    Vans[x] += ans[z];
    Vdet[x] += (long long)size[z] * size[z];
    star[x] += size[z];
    ch[x][1] = y;
    Vans[x] -= ans[y];
    Vdet[x] -= (long long)size[y] * size[y];
    star[x] -= size[y];
    update(x);
  }
}
void link(int x, int y) {
  access(y);
  splay(y);
  access(x);
  splay(x);
  fa[x] = y;
  Vans[y] += ans[x];
  Vdet[y] += (long long)size[x] * size[x];
  star[y] += size[x];
  update(y);
}
void cut(int x, int y) {
  access(y);
  splay(y);
  splay(x);
  Vans[y] -= ans[x];
  Vdet[y] -= (long long)size[x] * size[x];
  star[y] -= size[x];
  fa[x] = 0;
  update(y);
}
int in(int x, int y) {
  access(x);
  splay(x);
  splay(y);
  return not_root(x);
}
void duzide() {
  splay(1);
  printf("%.10f\n", (double)ans[1] / n / n);
}
int main() {
  read(n);
  for (int i = (2); i <= (n); ++i) read(p[i]);
  for (int i = (1); i <= (n); ++i) {
    read(w[i]);
    star[i] = size[i] = 1;
    ans[i] = psum[i] = w[i];
  }
  for (int i = (2); i <= (n); ++i) link(i, p[i]);
  duzide();
  read(q);
  while (q-- > 0) {
    scanf("%s", s + 0);
    if (s[0] == 'P') {
      read(v, u);
      if (in(u, v)) std::swap(u, v);
      cut(v, p[v]);
      p[v] = u;
      link(v, u);
    } else {
      read(x, y);
      access(x);
      splay(x);
      w[x] = y;
      update(x);
    }
    duzide();
  }
  return 0;
}
template <typename T>
void read(T &x) {
  x = 0;
  char c = getchar();
  T flag = 1;
  while (c < '0' || c > '9') {
    if (c == '-') flag = -flag;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  x *= flag;
}
template <typename T>
void read(T &x, T &y) {
  read(x);
  read(y);
}
template <typename T>
void read(T &x, T &y, T &z) {
  read(x);
  read(y);
  read(z);
}
template <typename T>
void writeC(T x) {
  if (x < 0) x = ~x + 1, putchar('-');
  if (x > 9) writeC(x / 10);
  putchar(x % 10 + '0');
}
template <typename T>
void write(T x) {
  writeC(x);
  putchar(' ');
}
template <typename T>
void writeN(T x) {
  writeC(x);
  puts("");
}