题目描述

A国的$n$个城市通过道路连接成一棵树，首都在编号为1的节点上。A国的物资都是从首都出发沿道路运输到每个城市，对于第$i$个城市，运输终中断的概率为$p_i$（保证不会在首都中断） ，现在要进行$q$次操作，每次更改一个城市的$p_i$，在所有更改结束后，输出每个城市获得物资的期望数量

输入输出格式

输入格式

第一行两个整数 $n,q,w$代表城市个数，操作次数，首都的物资数量

第二行$n$个整数，代表$p_1 - p_i$

接下来$n-1$行，每行两个整数$u,v$代表$u,v$间有连边

接下来$q$行每行两个整数$x,y$代表将点$x$的$p_i$改为$y$

输出格式

一行，$n$个整数，第$i$个代表第$i$个城市获得的期望物资数量

样例一

输入

3 2 10
1 0.5 0.5
1 2
2 3
2 1
3 1

输出

10.00 10.00 10.00

样例二

输入

5 2 10000
1.0 0.2 0.8 0.5 0.1
1 2
1 3
1 4
3 5
3 0.50
2 0.80

输出

10000.00 625.00 5000.00 8000.00 4000.00

数据范围

$1\le n,q \le 10^7$

$1 \le w \le 10^4$

$0 < p_i \le 1.0$