Problem Description

There are $n$ people in a group and $m$ pairs of friends among them. Currently, each person writes an integer on his hat. They plan to play the following game many times: everyone replaces his number on his hat with the average number of his number and all of his friends' numbers. That is, if before the game the person has $a_0$ written on his hat and a total of $k$ friends, each having number $a_1,...,a_k$, then after the game the number on his hat becomes $\dfrac{a_0+\cdots+a_k}{k+1}$. Note that numbers may become non-integers.

It can be proved that by playing more and more games, each number converges to a certain value. Given the initial numbers written on the hats, your task is to calculate these values.

Input

The first line contains the number of test cases $T$ $(1\le T\le 100)$.

For each test case, the first line contains two integers $n,m$ $(1\leq n,m\leq 10^5)$ .

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$ $(1\leq a_i\leq 10^8)$ , indicating the number on each hat.

Each of the following $m$ lines contains two integers $u,v$ $(1\le u,v\le n)$ , indicating a pair of friends.

It's guaranteed that there are no self-loop or multiple edges on the graph, and there are at most $20$ test cases such that $n > 1000$ or $m > 1000$.

Output

For each test case, output $n$ integers in $n$ lines, indicating the value of each person at last, and the result are reserved with 6 digits after the decimal point.

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

1.500000
1.500000
1.500000
1.500000
3.500000 
3.500000