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 N = 5e4 + 10;
int n, m;
int fa[N], num[N];
namespace LCT {
struct NODE {
  int fa, ch[2];
  int siz, ssiz;
  long long ssqr;
  long long sum, ans, sans;
  inline int& operator[](const int& i) { return ch[i]; }
} nod[N];
inline int Direc(const int& u) { return nod[nod[u].fa][1] == u; }
inline bool IfRoot(const int& u) {
  return nod[nod[u].fa][0] != u && nod[nod[u].fa][1] != u;
}
void SetChild(const int& fa, const int& d, const int& ch) {
  nod[fa][d] = ch;
  if (ch) nod[ch].fa = fa;
}
void PushUp(const int& u) {
  NODE &L = nod[nod[u][0]], &R = nod[nod[u][1]];
  nod[u].siz = L.siz + R.siz + nod[u].ssiz;
  nod[u].sum = L.sum + R.sum + 1ll * nod[u].ssiz * num[u];
  nod[u].ans = L.ans + R.ans + nod[u].sans +
               num[u] * ((1ll * (nod[u].ssiz) * (nod[u].ssiz)) - nod[u].ssqr) +
               num[u] * (2ll * nod[u].ssiz * R.siz) +
               2ll * L.sum * (R.siz + nod[u].ssiz);
}
void Rotate(const int& x) {
  int y = nod[x].fa, d = Direc(x);
  if (IfRoot(y))
    nod[x].fa = nod[y].fa;
  else
    SetChild(nod[y].fa, Direc(y), x);
  SetChild(y, d, nod[x][!d]);
  SetChild(x, !d, y);
  PushUp(y), PushUp(x);
}
void Splay(int x) {
  while (!IfRoot(x)) {
    int y = nod[x].fa;
    if (!IfRoot(y)) {
      if (Direc(x) == Direc(y))
        Rotate(y);
      else
        Rotate(x);
    }
    Rotate(x);
  }
  PushUp(x);
}
void ModifySub(const int& u, const int& v, const int& tim) {
  nod[u].ssiz += tim * nod[v].siz;
  nod[u].sans += tim * nod[v].ans;
  nod[u].ssqr += tim * (1ll * (nod[v].siz) * (nod[v].siz));
}
void Access(int x) {
  for (int y = 0; x; y = x, x = nod[x].fa) {
    Splay(x);
    ModifySub(x, nod[x][1], 1);
    SetChild(x, 1, y);
    ModifySub(x, nod[x][1], -1);
    PushUp(x);
  }
}
void Link(const int& x, const int& rt) {
  Access(x), Splay(x);
  Access(rt), Splay(rt);
  nod[rt].fa = x;
  ModifySub(x, rt, 1);
  PushUp(x);
}
void Cut(const int& fa, const int& x) {
  Access(fa), Splay(fa), Splay(x);
  nod[x].fa = 0;
  ModifySub(fa, x, -1);
  PushUp(fa);
}
bool IfAnc(const int& anc, const int& u) {
  Access(u), Splay(u), Splay(anc);
  return !IfRoot(u);
}
}  // namespace LCT
using LCT::Access;
using LCT::Cut;
using LCT::Link;
using LCT::nod;
using LCT::Splay;
int main() {
  scanf("%d", &n);
  for (int i = 2; i <= n; i++) scanf("%d", &fa[i]);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &num[i]);
    nod[i].siz = nod[i].ssiz = 1, nod[i].ans = nod[i].sum = num[i];
  }
  for (int i = 2; i <= n; i++) Link(fa[i], i);
  Access(1), Splay(1);
  printf("%.10f\n", 1.0 * nod[1].ans / n / n);
  scanf("%d", &m);
  while (m--) {
    char cmd[5] = {};
    scanf("%s", cmd);
    if (cmd[0] == 'P') {
      int u, v;
      scanf("%d%d", &u, &v);
      if (LCT::IfAnc(u, v)) swap(u, v);
      Cut(fa[u], u);
      Link(fa[u] = v, u);
      Access(1), Splay(1);
      printf("%.10f\n", 1.0 * nod[1].ans / n / n);
    } else {
      int u, key;
      scanf("%d%d", &u, &key);
      Access(u), Splay(u);
      num[u] = key;
      LCT::PushUp(u);
      printf("%.10f\n", 1.0 * nod[u].ans / n / n);
    }
  }
  return 0;
}