No tag edit access

E. ELCA

time limit per test

8 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 *p*_{v}. Also each vertex *v* has its integer value *s*_{v}.

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*p*_{v}=*u*. Otherwise you must perform assignment*p*_{u}=*v*. Note that after this query the graph continues to be a tree consisting of*n*vertexes. - V
*v**t*. Perform assignment*s*_{v}=*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·10^{4}) — the number of the tree vertexes.

The second line contains *n* - 1 integer *p*_{2}, *p*_{3}, ..., *p*_{n} (1 ≤ *p*_{i} ≤ *n*) — the description of the tree edges. It is guaranteed that those numbers form a tree.

The third line contains *n* integers — *s*_{1}, *s*_{2}, ... *s*_{n} (0 ≤ *s*_{i} ≤ 10^{6}) — the values written on each vertex of the tree.

The next line contains integer *q* (1 ≤ *q* ≤ 5·10^{4}) — 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* ≤ 10^{6}.

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 *p*_{u} = *v*. An example of such case is the last query in the sample.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2018 20:19:33 (d3).

Desktop version, switch to mobile version.

User lists

Name |
---|