4775 - 网管

经过推选，黎瑟莫名其妙的当上了计算机系的网管。上任后的黎瑟才发现，这里的网络经常断掉。给定一棵边权均 为1的无根树，点可能是黑色或白色，支持两种操作。 1 xi pi表示目前点xi的颜色可能发生了翻转(黑变白，白变黑)，发生概率为pi%。 2 si表示求E((∑x∈B dist(x,si))^2)，其中B为当前黑点的集合，dist(x,y)表示x号节点和y号节点在树上的最短 距离。

Input

第一行三个整数id,n,m，表示数据编号，树的点数和操作个数。 第二行n个整数ci，若ci=1表示点i为黑色，否则表示点i为白色。 接下来的n-1行，每行两个整数ui,vi，表示树上有一条ui节点到vi节点的边。 接下来的m行，每行表示一个操作，格式如题 1 <=id <=20 1 <=n <=Nid 0 <=m <=Nid 1 <=ui, vi, xi, si <=n 0 <=ci <=1 0 <=pi <=100

Output

对于每个询问输出一行一个浮点数表示答案，输出与答案绝对误 差不超过 10^-6 就算正确。

Examples

Input

1 100 100
1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 0 1 0
22 38
29 28
11 12
21 20
89 9
50 78
100 11
94 70
98 83
21 91
88 28
8 7
7 37
37 72
2 1
80 53
56 15
84 46
23 24
3 2
90 73
37 45
47 41
44 27
25 69
73 15
31 30
93 37
1 39
57 65
83 45
78 81
85 21
50 60
8 40
51 79
18 19
61 37
46 39
19 20
29 30
55 12
4 5
14 13
26 67
43 16
35 99
16 52
21 22
66 14
35 9
59 15
34 97
33 34
6 7
20 74
27 26
13 12
8 51
24 36
58 57
20 41
24 25
28 49
5 6
54 17
4 92
18 17
9 10
48 6
73 75
31 32
27 28
16 15
50 47
63 2
62 44
16 17
4 3
30 77
11 10
9 8
26 25
33 32
95 54
15 53
11 71
1 57
88 96
42 34
82 54
76 39
9 87
62 64
70 8
86 37
14 15
22 23
55 68
2 52
2 85
1 46 92
1 31 31
1 33 17
2 29
2 49
2 76
2 63
2 64
2 6
2 70
2 15
1 10 81
2 57
2 18
1 66 67
2 12
1 19 62
1 13 33
2 77
2 27
2 94
2 50
1 82 49
2 77
2 6
2 59
2 31
1 49 5
2 60
2 3
1 62 16
2 45
2 21
2 82
2 85
2 59
2 85
2 2
2 47
2 69
2 79
2 32
2 92
2 97
2 43
2 27
1 12 100
2 6
2 62
2 8
2 38
2 97
2 72
2 31
2 24
2 29
1 93 26
2 9
2 13
2 81
1 18 85
2 30
2 57
1 8 88
2 41
1 60 65
2 28
1 49 26
2 42
2 14
1 4 60
2 64
1 54 14
1 15 49
2 85
1 57 100
2 9
1 51 39
2 33
2 98
2 84
2 86
2 72
1 56 75
2 74
1 5 95
2 5
2 61
1 97 72
2 25
2 43
2 40
2 9
2 84
1 67 23
2 30
1 28 45
1 11 98

Output

285156.0000000000000
356409.0000000000000
633144.1888000000000
645494.1663999999900
795511.3296000000600
652911.3264000000200
744654.5341999999900
387472.5542000000100
379903.7423999999900
241023.5888000000000
722637.2878000000500
280453.3862000000100
262575.0398000000300
868854.3512000000300
560120.4240000000000
470363.8367999999900
500708.2392000000100
883592.7672000000000
420633.3348000000100
307082.7624000000100
876612.0191999999800
583093.3689999999500
571399.7776000000300
523911.4600000000200
344890.9564000000200
399381.5980000000000
412288.3829999999700
308954.6453999999800
412288.3829999999700
638584.7225999999800
440964.3962000000200
549969.2981999999600
482785.1850000000000
975195.7277999999900
599016.6239999999500
1317090.1503999999000
318628.1340000000200
569323.2412000000500
416242.4682000000000
706513.1548000000200
342447.8570000000200
427679.4048000000200
1264839.2104000000000
513831.8800000000000
842802.4816000000600
419775.2777999999800
678712.3175999999500
318367.8032000000200
266443.8376000000300
657353.4976000000000
786264.5753999999700
800298.0938000000300
361871.2289999999900
591276.2617999999800
1225657.3586800001000
246925.7472000000100
746625.2759999999500
378500.7612400000200
301318.1878000000100
952459.7794800000300
655201.7177999999800
956291.0853999999800
495966.3180399999800
495966.3180399999800
330354.1699999999800
442598.8577599999800
486953.4574400000300
434321.8692000000200
305110.6744799999900
414809.1759999999800
321591.6599999999700
995697.2360799999400
713643.6037599999700
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题