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;
namespace Patchouli {
const int N = 114514;
struct node {
  node *son[2], *father;
  long long size, sum_ans, sum_val, val, xsize, xans, xsum;
} t[N], *root, *null;
int f[N];
inline bool notroot(node *x) {
  return x->father->son[0] == x || x->father->son[1] == x;
}
inline int get(node *x) { return x->father->son[1] == x; }
inline void update(node *x) {
  x->size = x->son[0]->size + x->son[1]->size + x->xsize;
  x->sum_val = x->val * x->xsize + x->son[0]->sum_val + x->son[1]->sum_val;
  x->sum_ans = x->son[0]->sum_ans + x->son[1]->sum_ans + x->xans +
               x->val * (x->xsize * x->xsize - x->xsum) +
               2 * x->val * x->son[1]->size * x->xsize +
               2 * x->son[0]->sum_val * (x->size - x->son[0]->size);
}
inline void xchange(node *x, node *y, int o) {
  y->xsize += o * x->size;
  y->xans += o * x->sum_ans;
  y->xsum += o * x->size * x->size;
}
inline void rotate(node *x) {
  node *y = x->father, *z = y->father;
  int k = get(x);
  if (notroot(y)) z->son[get(y)] = x;
  x->father = z;
  y->son[k] = x->son[k ^ 1];
  y->son[k]->father = y;
  x->son[k ^ 1] = y;
  y->father = x;
  update(y);
}
inline void splay(node *x) {
  while (notroot(x)) {
    node *y = x->father;
    if (notroot(y)) rotate(get(x) ^ get(y) ? x : y);
    rotate(x);
  }
  update(x);
}
inline void access(node *x) {
  for (node *y = null; x != null; x = (y = x)->father) {
    splay(x);
    xchange(x->son[1], x, 1);
    x->son[1] = y;
    xchange(x->son[1], x, -1);
    update(x);
  }
}
inline void cut(node *x, node *y) {
  access(y);
  splay(y);
  splay(x);
  x->father = null;
  xchange(x, y, -1);
  update(y);
}
inline void link(node *x, node *y) {
  access(x);
  splay(x);
  access(y);
  splay(y);
  x->father = y;
  xchange(x, y, 1);
  update(y);
}
inline bool is_father(node *x, node *y) {
  access(x);
  node *tx = x, *ty = y;
  while (notroot(tx)) tx = tx->father;
  while (notroot(ty)) ty = ty->father;
  return tx == ty;
}
inline void init(int n) {
  null = t;
  null->son[0] = null->son[1] = null->father = null;
  for (int i = 1; i <= n; ++i) {
    t[i].son[0] = t[i].son[1] = t[i].father = null;
    t[i].xsize = t[i].size = 1;
  }
}
inline int read() {
  int a = 1, b = 0;
  char t;
  do {
    t = getchar();
    if (t == '-') a = -1;
  } while (t > '9' || t < '0');
  do {
    b = b * 10 - '0' + t;
    t = getchar();
  } while (t >= '0' && t <= '9');
  return a * b;
}
int QAQ() {
  int n = read();
  init(n);
  for (int i = 2; i <= n; ++i) f[i] = read();
  for (int i = 1; i <= n; ++i) t[i].val = t[i].sum_ans = t[i].sum_val = read();
  for (int i = 2; i <= n; ++i) link(t + i, t + f[i]);
  access(t + 1);
  splay(t + 1);
  printf("%.10lf\n", (double)t[1].sum_ans / (1ll * n * n));
  int m = read();
  while (m--) {
    char opt[4];
    scanf("%s", opt);
    if (opt[0] == 'P') {
      int x = read(), y = read();
      if (is_father(t + y, t + x)) {
        cut(t + y, t + f[y]);
        f[y] = x;
        link(t + y, t + f[y]);
      } else {
        cut(t + x, t + f[x]);
        f[x] = y;
        link(t + x, t + f[x]);
      }
    } else {
      node *x = t + read();
      access(x);
      splay(x);
      x->val = read();
      update(x);
    }
    access(t + 1);
    splay(t + 1);
    printf("%.10lf\n", (double)t[1].sum_ans / (1ll * n * n));
  }
  return false;
}
}  // namespace Patchouli
int main() { return Patchouli::QAQ(); }