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 std::cin;
using std::cout;
using std::endl;
using std::max;
using std::min;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::sort;
using std::vector;
const int maxN = 50000 + 233;
const long long maxA = 1000000 + 233;
int n, q;
long long a[maxN], cnt[maxN];
int p[maxN];
long long ans = 0;
namespace LinkCutTree {
struct Node;
Node *nil;
int cnt_splice = 0;
struct Node {
  int size;
  long long slope;
  long long sum_slope;
  int tag_dsize;
  long long dtimes;
  Node *fa, *ch[2];
  Node() : size(0), slope(0), sum_slope(0), tag_dsize(0), dtimes(0), fa(nil) {
    ch[0] = ch[1] = nil;
  }
  int id() { return (int)(this - nil); }
  void pushdown() {
    if (tag_dsize) {
      if (ch[0] != nil) {
        ch[0]->size += tag_dsize;
        ch[0]->tag_dsize += tag_dsize;
        ch[0]->id() == 1 ||
            (ch[0]->dtimes +=
             2LL * tag_dsize * (ch[0]->slope / a[p[ch[0]->id()]]));
      }
      if (ch[1] != nil) {
        ch[1]->size += tag_dsize;
        ch[1]->tag_dsize += tag_dsize;
        ch[1]->id() == 1 ||
            (ch[1]->dtimes +=
             2LL * tag_dsize * (ch[1]->slope / a[p[ch[1]->id()]]));
      }
      tag_dsize = 0;
    }
  }
  void maintain() { sum_slope = slope + ch[0]->sum_slope + ch[1]->sum_slope; }
  int relation() { return fa->ch[0] == this ? 0 : fa->ch[1] == this ? 1 : -1; }
  void rotate() {
    Node *f = fa, *ff = f->fa;
    int d = relation(), dd = f->relation();
    if (dd != -1) ff->ch[dd] = this;
    fa = ff;
    f->ch[d] = ch[d ^ 1];
    ch[d ^ 1]->fa = f;
    ch[d ^ 1] = f;
    f->fa = this;
    f->maintain();
    maintain();
  }
  void splay() {
    static Node *stk[maxN];
    int len = 0;
    stk[len++] = this;
    for (Node *o = fa; stk[len - 1]->relation() != -1; o = o->fa)
      stk[len++] = o;
    while (len) stk[--len]->pushdown();
    while (relation() != -1) {
      Node *f = fa;
      if (f->relation() == -1)
        rotate();
      else if (relation() == f->relation())
        f->rotate(), rotate();
      else
        rotate(), rotate();
    }
  }
  Node *outer_leftmost() {
    Node *o = this;
    while (o->relation() != -1) o = o->fa;
    o->pushdown();
    while (o->ch[0] != nil) o = o->ch[0], o->pushdown();
    return o;
  }
  Node *leftmost() {
    Node *o = this;
    o->pushdown();
    while (o->ch[0] != nil) o = o->ch[0], o->pushdown();
    return o;
  }
  Node *rightmost() {
    Node *o = this;
    o->pushdown();
    while (o->ch[1] != nil) o = o->ch[1], o->pushdown();
    return o;
  }
  void access() {
    Node *o = this;
    o->splay();
    o->lighten_son();
    o->maintain();
    cnt_splice = 0;
    while (1) {
      o = o->outer_leftmost();
      o->splay();
      if (o->fa == nil) break;
      ++cnt_splice;
      Node *f = o->fa;
      f->splay();
      f->lighten_son();
      f->strengthen_son(o);
    }
  }
  void lighten_son() {
    splay();
    if (ch[1] == nil) return;
    Node *son = ch[1]->leftmost();
    ch[1] = nil;
    son->splay();
    cnt[id()] += son->dtimes;
    son->dtimes = 0;
    son->slope = 0;
    son->maintain();
    maintain();
  }
  void strengthen_son(Node *son) {
    splay();
    son->splay();
    ch[1] = son;
    son->slope = (size - son->size) * a[id()];
    son->maintain();
    maintain();
  }
  void disconnect_son(Node *son) {
    access();
    splay();
    ans -= sum_slope * son->size * 2;
    size -= son->size;
    tag_dsize -= son->size;
    id() == 1 || (dtimes -= 2LL * son->size * (slope / a[p[id()]]));
    ans -= son->size * (long long)size * a[id()] * 2;
    cnt[id()] += -son->size * (long long)size * 2LL + son->dtimes;
    son->fa = nil;
  }
  void connect_son(Node *son) {
    access();
    splay();
    ans += sum_slope * son->size * 2;
    ans += son->size * (long long)size * a[id()] * 2;
    cnt[id()] += son->size * (long long)size * 2LL;
    size += son->size;
    tag_dsize += son->size;
    id() == 1 || (dtimes += 2LL * son->size * (slope / a[p[id()]]));
    son->fa = this;
  }
} nodes[maxN];
void init_lct() {
  nil = nodes;
  *nil = Node();
}
}  // namespace LinkCutTree
using namespace LinkCutTree;
vector<int> G[maxN];
void dfs(int u) {
  nodes[u].size = 1;
  cnt[u] = 1;
  for (int v : G[u]) {
    dfs(v);
    cnt[u] += nodes[v].size * nodes[u].size;
    nodes[u].size += nodes[v].size;
  }
  cnt[u] = cnt[u] * 2 - 1;
  ans += cnt[u] * a[u];
}
void initialize() {
  scanf("%d", &n);
  init_lct();
  for (int u = 1; u <= n; ++u) nodes[u] = Node();
  p[1] = -maxN;
  for (int u = 2; u <= n; ++u) {
    scanf("%d", &p[u]);
    (&nodes[u])->fa = (&nodes[p[u]]);
    G[p[u]].push_back(u);
  }
  for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
  dfs(1);
  printf("%.13lf\n", (double)ans / (double)((long long)n * n));
}
void modify_father(int x, int y) {
  Node *u = &nodes[x], *v = &nodes[y];
  (&nodes[p[x]])->lighten_son();
  (&nodes[p[x]])->disconnect_son(u);
  v->connect_son(u);
  p[x] = y;
}
void P_operation(int x, int y) {
  Node *v = &nodes[x], *u = &nodes[y];
  u->access();
  v->access();
  if (cnt_splice) {
    modify_father(x, y);
  } else {
    modify_father(y, x);
  }
}
void V_operation(int x, int val) {
  Node *u = &nodes[x];
  u->lighten_son();
  if (u->ch[0] != nil) {
    u->ch[0]->rightmost()->lighten_son();
  }
  ans += (val - a[x]) * cnt[x];
  a[x] = val;
  u->maintain();
}
void solve() {
  scanf("%d", &q);
  for (int kase = 1; kase <= q; ++kase) {
    char opt;
    scanf(" %c", &opt);
    if (opt == 'P') {
      int v, u;
      scanf("%d%d", &v, &u);
      P_operation(v, u);
    } else if (opt == 'V') {
      int u, x;
      scanf("%d%d", &u, &x);
      V_operation(u, x);
    } else {
      assert(false);
    }
    printf("%.13lf\n", (double)ans / (double)((long long)n * n));
  }
}
int main() {
  initialize();
  solve();
  return 0;
}