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 LL = long long;
const int N = 50000 + 5;
LL answer;
int n, m;
std::vector<int> edges[N];
struct Node *nill;
struct Node {
  Node *ch[2], *fa;
  int val, cnt, sbt, lazy;
  LL sum, pairs;
  void show() {}
  bool isroot() { return fa == nill || fa->ch[0] != this && fa->ch[1] != this; }
  bool d() { return fa->ch[1] == this; }
  void up() {
    if (this == nill) return;
    sum = ch[0]->sum + ch[1]->sum + (LL)cnt * val;
  }
  void make(int dt) {
    if (this == nill) return;
    pairs += (LL)cnt * dt * 2;
    sbt += dt;
    lazy += dt;
  }
  void down() {
    if (lazy) {
      ch[0]->make(lazy);
      ch[1]->make(lazy);
      lazy = 0;
    }
  }
  void D() {
    if (!isroot()) fa->D();
    down();
  }
  void setc(Node *p, int c) {
    ch[c] = p;
    p->fa = this;
    up();
  }
  void rot() {
    Node *f = fa, *ff = fa->fa;
    int c = d(), cc = fa->d();
    f->setc(ch[c ^ 1], c);
    this->setc(f, c ^ 1);
    if (ff->ch[cc] == f)
      ff->setc(this, cc);
    else
      this->fa = ff;
  }
  Node *splay() {
    for (D(); !isroot(); rot())
      if (!fa->isroot()) d() == fa->d() ? fa->rot() : rot();
    return this;
  }
  Node *access() {
    for (Node *p = this, *q = nill; p != nill; q = p, p = p->fa) {
      if (q != nill) {
        while (q->ch[0] != nill) q = q->ch[0];
        q->splay();
      }
      p->splay();
      p->cnt = p->sbt - q->sbt;
      p->setc(q, 1);
    }
    return splay();
  }
  Node *get_fa() {
    if (ch[0] == nill) return fa;
    Node *p = ch[0];
    while (p->ch[1] != nill) p = p->ch[1];
    return p;
  }
} dot[N];
void dfs(int u) {
  dot[u].cnt = 1;
  dot[u].pairs = 1;
  for (int v : edges[u]) {
    dfs(v);
    dot[u].pairs += (LL)dot[u].cnt * dot[v].cnt * 2;
    dot[u].cnt += dot[v].cnt;
  }
  dot[u].sbt = dot[u].cnt;
  dot[u].up();
  answer += dot[u].pairs * dot[u].val;
}
void move(int v, int u) {
  dot[u].access();
  dot[v].splay();
  if (dot[v].fa == nill) std::swap(u, v);
  Node *f = dot[v].get_fa()->access();
  f->cnt -= dot[v].sbt;
  f->make(-dot[v].sbt);
  f->up();
  answer -= f->sum * dot[v].sbt * 2;
  dot[u].access();
  answer += dot[u].sum * dot[v].sbt * 2;
  dot[u].make(dot[v].sbt);
  dot[u].cnt += dot[v].sbt;
  dot[u].up();
  dot[v].fa = dot + u;
}
int main() {
  scanf("%d", &n);
  nill = dot;
  for (int i = 0; i <= n; ++i) {
    dot[i].ch[0] = dot[i].ch[1] = dot[i].fa = nill;
  }
  for (int i = 2; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    edges[x].push_back(i);
    dot[i].fa = dot + x;
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &dot[i].val);
  }
  dfs(1);
  printf("%.13f\n", (double)answer / n / n);
  scanf("%d", &m);
  while (m--) {
    char op[2];
    int a, b;
    scanf("%s%d%d", op, &a, &b);
    if (op[0] == 'P') {
      move(a, b);
    } else {
      dot[a].access();
      answer += (LL)(b - dot[a].val) * dot[a].pairs;
      dot[a].val = b;
      dot[a].up();
    }
    printf("%.13f\n", (double)answer / n / n);
  }
  return 0;
}