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 maxn = 5e4 + 10;
namespace LCT {
struct node {
  node *ch[2], *par;
  int sz, lsz, tag, val;
  long long sum, way;
  node() {
    memset(ch, 0, sizeof ch);
    par = 0;
    sz = lsz = tag = val = 0;
    sum = way = 0;
  }
  inline bool isr() const {
    return !par || par->ch[0] != this && par->ch[1] != this;
  }
  inline int dir() const { return par->ch[1] == this; }
  inline void setc(int d, node* u) {
    ch[d] = u;
    if (u) {
      u->par = this;
    }
    return;
  }
  inline void pull() {
    sum = (long long)val * lsz;
    for (int i = 0; i < 2; ++i) {
      if (ch[i]) {
        sum += ch[i]->sum;
      }
    }
    return;
  }
  inline void M(int x) {
    way += 2ll * lsz * x;
    tag += x;
    sz += x;
    return;
  }
  inline void push() {
    if (tag) {
      for (int i = 0; i < 2; ++i) {
        if (ch[i]) {
          ch[i]->M(tag);
        }
      }
      tag = 0;
    }
    return;
  }
} pool[maxn];
inline void rot(node* u) {
  node* p = u->par;
  int d = u->dir();
  if (p->isr()) {
    u->par = p->par;
  } else {
    p->par->setc(p->dir(), u);
  }
  p->setc(d, u->ch[!d]);
  u->setc(!d, p);
  return p->pull();
}
inline void fix(node* u) {
  if (!u->isr()) {
    fix(u->par);
  }
  return u->push();
}
inline void splay(node* u) {
  fix(u);
  while (!u->isr()) {
    if (!u->par->isr()) {
      rot(u->dir() == u->par->dir() ? u->par : u);
    }
    rot(u);
  }
  return u->pull();
}
inline void access(node* u) {
  for (node* v = 0; u; u = u->par) {
    splay(u);
    u->lsz = u->sz;
    if (v) {
      while (v->ch[0]) {
        v = v->ch[0];
      }
      splay(v);
      u->lsz -= v->sz;
    }
    u->ch[1] = v;
    (v = u)->pull();
  }
  return;
}
}  // namespace LCT
vector<int> g[maxn];
long long ans;
int par[maxn];
int n;
inline void dfs(int u) {
  auto& x = LCT::pool[u];
  x.sz = 1;
  x.lsz = 1;
  x.way = 1;
  for (int& v : g[u]) {
    dfs(v);
    auto& y = LCT::pool[v];
    x.way += 2ll * y.sz * x.sz;
    x.sz += y.sz;
    x.lsz += y.sz;
  }
  ans += x.way * x.val;
  return x.pull();
}
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; ++i) {
    scanf("%d", par + i);
    LCT::pool[i].par = LCT::pool + par[i];
    g[par[i]].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &LCT::pool[i].val);
  }
  dfs(1);
  double mu = 1. / ((double)n * n);
  printf("%.12f\n", (double)ans * mu);
  int q;
  scanf("%d", &q);
  while (q--) {
    char c = getchar();
    while (c != 'P' && c != 'V') {
      c = getchar();
    }
    if (c == 'P') {
      int u, v;
      scanf("%d%d", &v, &u);
      auto x = LCT::pool + u, y = LCT::pool + v;
      LCT::access(x);
      LCT::splay(y);
      if (y->par) {
        swap(u, v);
        swap(x, y);
      }
      auto z = LCT::pool + par[u];
      LCT::access(z);
      LCT::splay(z);
      LCT::splay(x);
      z->lsz -= x->sz;
      z->pull();
      z->M(-x->sz);
      ans -= 2ll * z->sum * x->sz;
      LCT::access(y);
      LCT::splay(y);
      ans += 2ll * y->sum * x->sz;
      y->M(x->sz);
      y->lsz += x->sz;
      x->par = y;
      par[u] = v;
    } else {
      int u, w;
      scanf("%d%d", &u, &w);
      LCT::splay(LCT::pool + u);
      ans += LCT::pool[u].way * (w - LCT::pool[u].val);
      LCT::pool[u].val = w;
    }
    printf("%.12f\n", (double)ans * mu);
  }
  return 0;
}