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 infi = 2147483647;
const int mod = 1000000007;
const double eps = 1e-6;
const int N = 100010;
int n, m, g[N], to[N], nxt[N], tot;
long long ANS, TOT;
struct seg* null;
struct seg {
  seg* fa;
  seg* son[2];
  int sz, v, size, lazy;
  long long SZ, sum;
  inline void new_node() {
    fa = son[0] = son[1] = null;
    sum = SZ = 0;
    sz = size = lazy = v = 0;
  }
  inline bool isroot() {
    return (fa == null) || (fa->son[0] != this && fa->son[1] != this);
  }
  inline void add(int x) {
    if (this == null) return;
    size += x;
    SZ += 2ll * x * sz;
    lazy += x;
  }
  inline void clean() {
    if (this == null) return;
    if (lazy) {
      son[0]->add(lazy);
      son[1]->add(lazy);
      lazy = 0;
    }
  }
  inline void updata() { sum = (long long)sz * v + son[0]->sum + son[1]->sum; }
  inline void rotate() {
    seg *x = this, *y = x->fa;
    int w = (y->son[0] == x);
    if (!y->isroot()) {
      seg* z = y->fa;
      if (z->son[0] == y) z->son[0] = x;
      if (z->son[1] == y) z->son[1] = x;
    }
    x->fa = y->fa;
    y->fa = x;
    if (x->son[w] != null) x->son[w]->fa = y;
    y->son[w ^ 1] = x->son[w];
    x->son[w] = y;
    y->updata();
  }
  inline void clear() {
    if (!isroot()) fa->clear();
    clean();
  }
  inline void splay() {
    seg *x = this, *y, *z;
    clear();
    while (!isroot()) {
      y = x->fa;
      z = y->fa;
      if (!y->isroot())
        if ((z->son[0] == y) ^ (y->son[1] == x))
          y->rotate();
        else
          rotate();
      rotate();
    }
    updata();
  }
  inline void access() {
    seg *x = this, *y = null;
    for (; x != null; y = x, x = x->fa) {
      if (y != null) {
        while (y->son[0] != null) y = y->son[0];
        y->splay();
      }
      x->splay();
      x->sz = x->size - y->size;
      x->son[1] = y;
      if (y != null) y->fa = x;
      x->updata();
    }
  }
};
seg pool[N];
seg* v[N];
seg* cur;
void clear() {
  ANS = 0;
  cur = pool;
  null = cur++;
  null->new_node();
}
inline void addedge(int x, int y) {
  to[++tot] = y;
  nxt[tot] = g[x];
  g[x] = tot;
}
inline void dfs(int x, int dep) {
  v[x]->size = 1;
  for (int k = g[x]; k; k = nxt[k]) {
    dfs(to[k], dep + 1);
    v[x]->SZ += (long long)v[x]->size * v[to[k]]->size;
    v[x]->size += v[to[k]]->size;
  }
  v[x]->SZ = (v[x]->SZ << 1 | 1);
  ANS += v[x]->SZ * v[x]->v;
  v[x]->sz = v[x]->size;
}
inline void cut(int x) {
  v[x]->access();
  v[x]->splay();
  seg* y = v[x]->son[0];
  ANS -= 2ll * y->sum * v[x]->size;
  y->add(-v[x]->size);
  v[x]->son[0]->fa = null;
  v[x]->son[0] = null;
  v[x]->updata();
  y->updata();
}
inline void link(int x, int y) {
  v[y]->access();
  v[y]->splay();
  ANS += 2ll * v[y]->sum * v[x]->size;
  v[y]->add(v[x]->size);
  v[y]->updata();
  v[x]->fa = v[y];
}
int main() {
  int i, x, y, k, t;
  char s[10];
  scanf("%d", &n);
  clear();
  for (i = 1; i <= n; i++) {
    v[i] = cur++;
    v[i]->new_node();
  }
  for (i = 2; i <= n; i++) {
    scanf("%d", &x);
    addedge(x, i);
    v[i]->fa = v[x];
  }
  for (i = 1; i <= n; i++) scanf("%d", &v[i]->v);
  dfs(1, 0);
  TOT = (long long)n * n;
  printf("%.10lf\n", (double)ANS / TOT);
  scanf("%d", &m);
  for (i = 1; i <= m; i++) {
    scanf("%s%d%d", &s, &x, &y);
    if (s[0] == 'P') {
      v[y]->access();
      v[x]->splay();
      if (v[x]->fa == null) swap(x, y);
      cut(x);
      link(x, y);
    } else if (s[0] == 'V') {
      v[x]->access();
      v[x]->splay();
      ANS += v[x]->SZ * (y - v[x]->v);
      v[x]->v = y;
      v[x]->updata();
    }
    printf("%.10lf\n", (double)ANS / TOT);
  }
  return 0;
}