题目描述

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\)