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 = 50050;
int fa[N], go[N][2], sub[N], ssz[N], val[N];
long long zsv[N], stc[N], lzy[N];
void upd(int x, long long f) {
  if (x) stc[x] -= sub[x] * f, lzy[x] += f;
}
void push(int x) {
  if (lzy[x]) upd(go[x][0], lzy[x]), upd(go[x][1], lzy[x]), lzy[x] = 0;
}
void pull(int x) {
  ssz[x] = ssz[go[x][0]] + sub[x] + ssz[go[x][1]];
  zsv[x] = zsv[go[x][0]] + (long long)val[x] * sub[x] + zsv[go[x][1]];
}
int pd(int x) { return go[fa[x]][0] == x ? 0 : go[fa[x]][1] == x ? 1 : -1; }
void rot(int x) {
  int y = fa[x], z = fa[y], p = pd(x), q = pd(y), w = go[x][p ^ 1];
  if (~q) go[z][q] = x;
  go[x][p ^ 1] = y;
  go[y][p] = w;
  if (w) fa[w] = y;
  fa[y] = x;
  fa[x] = z;
  pull(y);
  pull(x);
}
void cl(int x) {
  if (~pd(x)) cl(fa[x]);
  push(x);
}
void splay(int x) {
  for (cl(x); ~pd(x); rot(x))
    if (~pd(fa[x])) rot(pd(x) == pd(fa[x]) ? fa[x] : x);
}
void access(int x) {
  splay(x);
  sub[x] += ssz[go[x][1]];
  go[x][1] = 0;
  pull(x);
  for (; fa[x]; rot(x)) {
    splay(fa[x]);
    sub[fa[x]] += ssz[go[fa[x]][1]];
    sub[fa[x]] -= ssz[x];
    go[fa[x]][1] = x;
    pull(fa[x]);
  }
}
int p[N], sz[N];
long long now[N], ans;
vector<int> E[N];
void DFS(int u) {
  sz[u] = 1;
  for (int v : E[u]) DFS(v), sz[u] += sz[v], now[u] -= (long long)sz[v] * sz[v];
  now[u] += (long long)sz[u] * sz[u];
}
int main() {
  int n;
  scanf("%i", &n);
  for (int i = 2; i <= n; i++) scanf("%i", &p[i]), E[p[i]].push_back(i);
  DFS(1);
  for (int i = 1; i <= n; i++) {
    scanf("%i", &val[i]);
    fa[i] = p[i];
    sub[i] = sz[i];
    stc[i] = now[i];
    pull(i);
    ans += now[i] * val[i];
  }
  printf("%.15f\n", (double)ans / n / n);
  int q;
  scanf("%i", &q);
  while (q--) {
    int x, y;
    char t;
    scanf("\n%c %i %i", &t, &x, &y);
    if (t == 'P') {
      access(y);
      splay(x);
      if (!fa[x]) swap(x, y);
      int z = p[x];
      access(z);
      sub[z] -= ssz[x];
      fa[x] = 0;
      pull(z);
      upd(z, ssz[x] * 2);
      ans -= zsv[z] * ssz[x] * 2;
      access(y);
      upd(y, -ssz[x] * 2);
      ans += zsv[y] * ssz[x] * 2;
      sub[y] += ssz[x];
      pull(y);
      fa[x] = y;
      p[x] = y;
    } else {
      splay(x);
      ans -= stc[x] * val[x];
      val[x] = y;
      ans += stc[x] * val[x];
      pull(x);
    }
    printf("%.15f\n", (double)ans / n / n);
  }
  return 0;
}