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;
template <typename T, typename U>
inline void smin(T &a, const U &b) {
  if (a > b) a = b;
}
template <typename T, typename U>
inline void smax(T &a, const U &b) {
  if (a < b) a = b;
}
template <class T>
inline void gn(T &first) {
  char c, sg = 0;
  while (c = getchar(), (c > '9' || c < '0') && c != '-')
    ;
  for ((c == '-' ? sg = 1, c = getchar() : 0), first = 0; c >= '0' && c <= '9';
       c = getchar())
    first = (first << 1) + (first << 3) + c - '0';
  if (sg) first = -first;
}
template <class T1, class T2>
inline void gn(T1 &x1, T2 &x2) {
  gn(x1), gn(x2);
}
int power(int a, int b, int m, int ans = 1) {
  for (; b; b >>= 1, a = 1LL * a * a % m)
    if (b & 1) ans = 1LL * ans * a % m;
  return ans;
}
bool rev[55000];
int pa[55000], son[55000][2];
int val[55000], cnt[55000], sum[55000];
int up[55000];
long long ss[55000], tot[55000];
void push_up(int first) {
  int L = son[first][0], R = son[first][1];
  sum[first] = cnt[first];
  ss[first] = (long long)cnt[first] * val[first];
  if (L) sum[first] += sum[L], ss[first] += ss[L];
  if (R) sum[first] += sum[R], ss[first] += ss[R];
}
void add_up(int first, int v) {
  if (!first) return;
  up[first] += v;
  tot[first] += 2LL * v * cnt[first];
}
void push_down(int first) {
  if (up[first]) {
    add_up(son[first][0], up[first]);
    add_up(son[first][1], up[first]);
    up[first] = 0;
  }
}
bool isroot(int first) {
  return son[pa[first]][0] != first && son[pa[first]][1] != first;
}
void down(int first) {
  if (!isroot(first)) down(pa[first]);
  push_down(first);
}
void rot(int first, int d) {
  int second = pa[first], z = pa[second];
  son[second][!d] = son[first][d];
  pa[son[first][d]] = second;
  pa[first] = pa[second];
  if (son[z][0] == second)
    son[z][0] = first;
  else if (son[z][1] == second)
    son[z][1] = first;
  pa[second] = first;
  son[first][d] = second;
  push_up(second);
}
void splay(int first) {
  down(first);
  while (!isroot(first)) {
    if (isroot(pa[first]))
      rot(first, son[pa[first]][0] == first);
    else {
      int second = pa[first], z = pa[second];
      int d = (son[z][0] == second);
      son[second][d] == first ? rot(first, !d) : rot(second, d);
      rot(first, d);
    }
  }
  push_up(first);
}
void access(int first) {
  for (int second = 0; first; first = pa[first]) {
    splay(first);
    cnt[first] += sum[son[first][1]];
    cnt[first] -= sum[second];
    son[first][1] = second;
    push_up(second = first);
  }
}
bool isancestor(int u, int v) {
  access(v);
  splay(u);
  return pa[u] == 0;
}
vector<int> adj[55000];
long long ans;
void dfs(int u) {
  cnt[u] = 1;
  for (int v : adj[u]) {
    dfs(v);
    cnt[u] += cnt[v];
    tot[u] -= (long long)cnt[v] * cnt[v];
  }
  push_up(u);
  tot[u] += (long long)cnt[u] * cnt[u];
  ans += tot[u] * val[u];
}
int fa[55000];
int main() {
  int n;
  cin >> n;
  for (int i = 2; i <= n; i++) {
    gn(fa[i]);
    adj[pa[i] = fa[i]].push_back(i);
  }
  for (int i = 1; i <= n; i++) gn(val[i]);
  dfs(1);
  double first = 1.0 / n / n;
  printf("%.9lf\n", (double)ans * first);
  int m;
  char op;
  int u, v;
  for (cin >> m; m--; printf("%.9lf\n", (double)ans * first)) {
    scanf(" %c", &op);
    gn(u, v);
    if (op == 'P') {
      if (isancestor(u, v)) swap(u, v);
      int f = fa[u];
      if (f == v) continue;
      access(f);
      splay(f);
      splay(u);
      cnt[f] -= sum[u];
      push_up(f);
      ans -= 2 * ss[f] * sum[u];
      add_up(f, -sum[u]);
      access(v);
      splay(v);
      ans += 2 * ss[v] * sum[u];
      add_up(v, sum[u]);
      cnt[v] += sum[u];
      push_up(v);
      fa[u] = pa[u] = v;
    } else {
      splay(u);
      ans += (v - val[u]) * tot[u];
      val[u] = v;
      push_up(u);
    }
  }
  return 0;
}