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 N, M;
int pfa[100005], fa[100005], son[100005][2];
long long ans, size[100005], sum[100005], all[100005];
long long cnt[100005], val[100005], tag[100005];
vector<int> dn[100005];
char ss[20];
void Update(int x) {
  size[x] = size[son[x][0]] + size[son[x][1]] + cnt[x];
  sum[x] = sum[son[x][0]] + sum[son[x][1]] + val[x] * cnt[x];
}
void Set_tag(int x, int ad) {
  all[x] += cnt[x] * ad;
  tag[x] += ad;
}
void Push_down(int x) {
  if (tag[x]) {
    if (son[x][0]) Set_tag(son[x][0], tag[x]);
    if (son[x][1]) Set_tag(son[x][1], tag[x]);
    tag[x] = 0;
  }
}
void Rotate(int x, int d) {
  int tmp = fa[x];
  pfa[x] = pfa[tmp], pfa[tmp] = 0;
  son[tmp][d ^ 1] = son[x][d], fa[son[x][d]] = tmp;
  if (fa[tmp]) son[fa[tmp]][son[fa[tmp]][1] == tmp] = x;
  fa[x] = fa[tmp], fa[tmp] = x, son[x][d] = tmp;
  Update(tmp), Update(x);
}
void Splay(int x, int to) {
  Push_down(x);
  int tmp, d1, d2;
  while ((tmp = fa[x]) != to) {
    if (fa[tmp]) Push_down(fa[tmp]);
    Push_down(tmp), Push_down(x);
    if (fa[tmp] == to)
      Rotate(x, son[tmp][0] == x);
    else if ((d1 = (son[tmp][0] == x)) != (d2 = (son[fa[tmp]][0] == tmp)))
      Rotate(x, d1), Rotate(x, d2);
    else
      Rotate(tmp, d2), Rotate(x, d1);
  }
}
void Split(int x) {
  Splay(x, 0);
  if (son[x][0]) {
    cnt[x] += size[son[x][0]];
    pfa[son[x][0]] = x;
    fa[son[x][0]] = 0, son[x][0] = 0;
    Update(x);
  }
}
void Merge(int x, int y) {
  Split(x), Splay(y, 0);
  cnt[x] -= size[y];
  pfa[y] = 0;
  fa[y] = x, son[x][0] = y;
  Update(x);
}
int Access(int x) {
  Split(x);
  int tmp = x;
  for (x = pfa[x]; x; tmp = x, x = pfa[x]) Merge(x, tmp);
  return tmp;
}
void Change(int x, int to) {
  Splay(x, 0);
  ans += (to - val[x]) * all[x];
  val[x] = to;
  Update(x);
}
int Get_fa(int x) {
  Splay(x, 0);
  if (!son[x][1]) return pfa[x];
  for (x = son[x][1]; son[x][0]; x = son[x][0])
    ;
  return x;
}
void Work(int x, int y) {
  int tmp;
  Access(x), tmp = Access(y);
  if (tmp != x) swap(x, y);
  tmp = Get_fa(y);
  Access(tmp), Splay(tmp, 0), Splay(y, 0);
  cnt[tmp] -= size[y], Update(tmp);
  pfa[y] = 0, ans -= 2 * sum[tmp] * size[y];
  Set_tag(tmp, -2 * size[y]);
  Access(x), Splay(x, 0);
  pfa[y] = x, ans += 2 * sum[x] * size[y];
  Set_tag(x, 2 * size[y]);
  cnt[x] += size[y], Update(x);
}
void Dfs(int x) {
  int tmp, i;
  cnt[x] = 1, all[x] = 1;
  for (i = 0; i < dn[x].size(); i++) {
    Dfs(tmp = dn[x][i]);
    all[x] += cnt[x] * cnt[tmp] * 2;
    cnt[x] += cnt[tmp];
  }
  ans += all[x] * val[x];
  Update(x);
}
int main() {
  int i, j, tmp, fr, to;
  scanf("%d", &N);
  for (i = 2; i <= N; i++) scanf("%d", &pfa[i]), dn[pfa[i]].push_back(i);
  for (i = 1; i <= N; i++) scanf("%d", &val[i]);
  Dfs(1);
  printf("%.10lf\n", ans * 1.0 / N / N);
  scanf("%d", &M);
  for (i = 1; i <= M; i++) {
    scanf("%s %d %d", ss, &fr, &to);
    if (ss[0] == 'P')
      Work(fr, to);
    else
      Change(fr, to);
    printf("%.10lf\n", ans * 1.0 / N / N);
  }
  return 0;
}