有一个包含 $n$ 个人的群体，其中有 $m$ 对朋友关系。目前，每个人都在自己的帽子上写了一个整数。他们计划进行多次以下游戏：每个人将自己帽子上的数字替换为自己原本的数字与所有朋友数字的平均值。也就是说，如果游戏开始前某人帽子上的数字为 $a_0$，且他共有 $k$ 个朋友，这些朋友帽子上的数字分别为 $a_1, \dots, a_k$，那么游戏结束后，他帽子上的数字变为 $(a_0 + \dots + a_k)/(k+1)$。注意，数字可能会变为非整数。

可以证明，随着游戏次数的增加，每个数字都会收敛到一个特定的值。给定帽子上初始的数字，你的任务是计算这些收敛后的值。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 100$)。

对于每个测试用例，第一行包含两个整数 $n, m$ ($1 \le n, m \le 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$)，表示每个人帽子上的初始数字。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示一对朋友关系。

保证图中没有自环或重边，且满足 $n > 1000$ 或 $m > 1000$ 的测试用例最多有 20 个。

输出格式

对于每个测试用例，输出 $n$ 行，每行一个实数，表示每个人最终的数值。结果应保留小数点后 6 位。

样例

输入 1

2
2 1
1 2
1 2
4 2
1 2 3 4
1 2
3 4

输出 1

1.500000
1.500000
1.500000
1.500000
3.500000
3.500000