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;
int read() {
  bool f = 0;
  int x = 0;
  char c = getchar();
  while (c < '0' || '9' < c) {
    if (c == '-') f = 1;
    c = getchar();
  }
  while ('0' <= c && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return !f ? x : -x;
}
const int MAXN = 200000;
const int INF = 0x3f3f3f3f;
int fa[MAXN + 5], ch[MAXN + 5][2];
long long a[MAXN + 5], siz[MAXN + 5], sum[MAXN + 5], ans[MAXN + 5],
    all[MAXN + 5], ad[MAXN + 5], de[MAXN + 5];
bool pan(int u) { return ch[fa[u]][1] == u; }
bool isroot(int u) { return (ch[fa[u]][0] != u && ch[fa[u]][1] != u); }
void PushUp(int u) {
  sum[u] = sum[ch[u][0]] + sum[ch[u][1]] + siz[u];
  all[u] = all[ch[u][0]] + all[ch[u][1]] + siz[u] * a[u];
  ans[u] = ans[ch[u][0]] + ans[ch[u][1]] + ad[u] +
           a[u] * (siz[u] * siz[u] - de[u]) +
           2 * a[u] * siz[u] * sum[ch[u][1]] +
           2 * all[ch[u][0]] * (sum[u] - sum[ch[u][0]]);
  return;
}
void Rotate(int x) {
  int y = fa[x], z = fa[y], dx = pan(x), dy = pan(y), w = ch[x][dx ^ 1];
  if (!isroot(y)) ch[z][dy] = x;
  ch[x][dx ^ 1] = y, ch[y][dx] = w;
  if (w) fa[w] = y;
  fa[y] = x, fa[x] = z;
  PushUp(y);
  return;
}
void Splay(int x) {
  for (int y = fa[x]; !isroot(x); Rotate(x), y = fa[x])
    if (!isroot(y)) Rotate(pan(x) == pan(y) ? y : x);
  PushUp(x);
  return;
}
int Access(int x) {
  int y = 0;
  while (x) {
    Splay(x);
    siz[x] -= sum[y];
    ad[x] -= ans[y];
    de[x] -= sum[y] * sum[y];
    siz[x] += sum[ch[x][1]];
    ad[x] += ans[ch[x][1]];
    de[x] += sum[ch[x][1]] * sum[ch[x][1]];
    ch[x][1] = y, PushUp(x), y = x, x = fa[x];
  }
  return y;
}
void Link(int x, int y) {
  Access(y);
  Splay(y);
  Access(x);
  Splay(x);
  fa[y] = x;
  siz[x] += sum[y];
  ad[x] += ans[y];
  de[x] += 1ll * sum[y] * sum[y];
  PushUp(x);
  return;
}
void Cut(int x, int y) {
  Access(x);
  Splay(x);
  Splay(y);
  siz[x] -= sum[y];
  ad[x] -= ans[y];
  de[x] -= 1ll * sum[y] * sum[y];
  fa[y] = 0;
  PushUp(x);
  return;
}
char Re[5];
int f[MAXN + 5];
bool check(int x, int y) {
  Access(y);
  Splay(y), Splay(x);
  return !isroot(y);
}
int main() {
  int n = read();
  for (int i = 2; i <= n; i++) f[i] = read();
  for (int i = 1; i <= n; i++)
    a[i] = read(), sum[i] = siz[i] = 1, ans[i] = all[i] = a[i];
  for (int i = 2; i <= n; i++) Link(f[i], i);
  Access(1), Splay(1);
  printf("%.10f\n", 1.0 * ans[1] / n / n);
  int m = read();
  for (int i = 1; i <= m; i++) {
    scanf("%s", Re);
    if (Re[0] == 'P') {
      int x = read(), y = read();
      if (f[x] == y || f[y] == x) goto Break;
      if (check(x, y)) swap(x, y);
      Cut(f[x], x), f[x] = y;
      Link(f[x], x);
    } else {
      int x = read(), y = read();
      Access(x), Splay(x);
      a[x] = y;
      PushUp(x);
    }
  Break:
    Access(1), Splay(1);
    printf("%.10f\n", 1.0 * ans[1] / n / n);
  }
  return 0;
}