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;
struct node {
  node *l, *r, *p;
  long long v, s, z, w, t, k, i;
  node(long long v, long long i)
      : l(0), r(0), p(0), v(v), s(1), z(0), w(0), t(v), k(1), i(i) {}
};
inline bool is_root(node *n) {
  return n->p == NULL || n->p->l != n && n->p->r != n;
}
inline bool left(node *n) { return n == n->p->l; }
inline long long size(node *n) { return n ? n->s + n->z : 0; }
inline long long tot(node *n) { return n ? n->t : 0; }
inline void push(node *n) {
  n->s += n->z;
  n->w += n->z;
  n->k += 2 * n->z * (n->s - n->w);
  if (n->l) n->l->z += n->z;
  if (n->r) n->r->z += n->z;
  n->z = 0;
}
inline void update(node *n) {
  push(n);
  n->t = tot(n->l) + tot(n->r) + n->v * (n->s - n->w);
}
inline void connect(node *n, node *p, bool l) {
  (l ? p->l : p->r) = n;
  if (n) n->p = p;
}
inline void rotate(node *n) {
  node *p = n->p, *g = p->p;
  bool l = left(n);
  connect(l ? n->r : n->l, p, l);
  if (!is_root(p))
    connect(n, g, left(p));
  else
    n->p = g;
  connect(p, n, !l);
  update(p), update(n);
}
inline void splay(node *n) {
  while (!is_root(n)) {
    node *p = n->p, *g = p->p;
    if (!is_root(p)) push(g);
    push(p), push(n);
    if (!is_root(p)) rotate(left(n) ^ left(p) ? n : p);
    rotate(n);
  }
  push(n);
}
inline node *find_root(node *n) {
  if (n == NULL) return NULL;
  while (n->l) {
    push(n);
    n = n->l;
  }
  return n;
}
inline node *expose(node *n) {
  node *last = NULL;
  for (node *m = n; m; m = m->p) {
    splay(m);
    m->w = size(find_root(last));
    m->r = last;
    last = m;
    update(m);
  }
  splay(n);
  return last;
}
void link(node *m, node *n) {
  expose(m), expose(n);
  m->p = n;
  n->z += size(m);
}
void cut(node *n) {
  expose(n);
  n->l->z -= size(n);
  n->l->p = NULL;
  n->l = NULL;
}
node *lca(node *m, node *n) {
  expose(m);
  return expose(n);
}
const int MAXN = 50005;
long long N, M, P[MAXN], A, B, ans;
char C;
node *V[MAXN];
void print(node *n, int d = 0, bool r = 1) {
  if (n == NULL) {
    for (int i = 0; i < d; i++) cout << "  ";
    cout << "x\n";
    if (r) cout << "---\n";
    return;
  }
  print(n->l, d + 1, 0);
  for (int i = 0; i < d; i++) cout << "  ";
  cout << n->i << ": " << n->k;
  if (is_root(n)) cout << " (" << (n->p ? n->p->i : -1) << ") ";
  cout << '\n';
  print(n->r, d + 1, r);
}
void print() {
  for (int i = 0; i < N; i++) {
    if (is_root(V[i])) {
      print(V[i]);
    }
  }
  cout << endl << endl;
}
int main() {
  cin >> N;
  cout << fixed << setprecision(9);
  for (int i = 1; i < N; i++) {
    cin >> P[i];
    P[i]--;
  }
  for (int i = 0; i < N; i++) {
    int v;
    cin >> v;
    V[i] = new node(v, i);
    ans += v;
  }
  for (int i = 1; i < N; i++) {
    link(V[i], V[P[i]]);
    ans += 2 * tot(V[P[i]]) * size(V[i]);
  }
  cout << 1.0 * ans / N / N << '\n';
  cin >> M;
  while (M--) {
    cin >> C >> A >> B;
    if (C == 'P') {
      node *v = V[A - 1], *u = V[B - 1];
      if (lca(u, v) == v) swap(u, v);
      expose(v);
      ans -= 2 * tot(v->l) * size(v);
      cut(v);
      link(v, u);
      ans += 2 * tot(u) * size(v);
    } else {
      node *v = V[A - 1];
      expose(v);
      update(v);
      ans += (B - v->v) * v->k;
      v->v = B;
    }
    cout << 1.0 * ans / N / N << '\n';
  }
}