Bessie 正在一个由 $N$ ($2\le N\le 10^4$) 个岛屿组成的网络中度假，这些岛屿被 $M$ 条双向桥梁连接，每条桥梁连接两个岛屿 ($N-1\le M\le 3/2(N-1)$)。保证这些桥梁构成一个连通的简单图（特别地，没有两条桥梁连接同一对岛屿，也没有桥梁连接岛屿自身）。

同时保证没有任何一条桥梁位于多于一个简单环上。简单环是指不包含重复岛屿的环。

Bessie 从岛屿 $1$ 开始，按照以下步骤旅行。假设她当前位于岛屿 $i$：

1. 如果岛屿 $i$ 周围没有她尚未经过的桥梁，她结束度假。
2. 否则，以 $p_i\pmod{10^9+7}$ 的概率，她结束度假。
3. 否则，在她所有尚未经过的邻接桥梁中，她等概率地随机选择一条并穿过它。

对于每个岛屿，输出她最终在那个岛屿结束度假的概率，对 $10^9+7$ 取模。

输入格式

第一行包含独立测试用例的数量 $T$ ($1\le T\le 10$)。连续的测试用例之间由空行分隔。

每个测试用例的第一行包含 $N$ 和 $M$，其中 $N$ 是岛屿数量，$M$ 是桥梁数量。保证所有测试用例的 $N$ 之和不超过 $10^4$。

每个测试用例的第二行包含 $p_1, p_2,\dots, p_N$ ($0\le p_i<10^9+7$)。

接下来的 $M$ 行描述桥梁。第 $i$ 行包含整数 $u_i$ 和 $v_i$ ($1\le u_i

输出格式

对于每个测试用例，在一行内输出从 $1$ 到 $N$ 每个岛屿结束度假的概率，对 $10^9+7$ 取模，并用空格分隔。

样例

样例输入 1

2

3 2
0 10 111111112
1 3
2 3

6 5
500000004 0 0 0 0 0
1 5
1 3
4 5
5 6
1 2

样例输出 1

0 888888896 111111112
500000004 166666668 166666668 83333334 0 83333334

说明 1

对于第一个测试用例，$p_3\equiv 1/9 \pmod{10^9+7}$。Bessie 在 $3$ 结束度假的概率为 $1/9$（路径 $1\to 3$），在 $2$ 结束度假的概率为 $8/9$（路径 $1\to 3\to 2$）。

对于第二个测试用例，$p_1\equiv 1/2\pmod{10^9+7}$。Bessie 在 $1$ 结束度假的概率为 $1/2$，在 $2$ 或 $3$ 结束度假的概率各为 $1/6$，在 $4$ 或 $6$ 结束度假的概率各为 $1/12$。

样例输入 2

2

5 5
333333336 333333336 0 0 0
1 2
2 3
3 4
4 5
1 5

5 5
0 0 0 0 0
1 2
2 3
2 4
1 4
1 5

样例输出 2

777777784 222222224 0 0 0
0 0 333333336 0 666666672

说明 2

对于第一个测试用例，$p_1\equiv p_2\equiv 1/3\pmod{10^9+7}$。Bessie 在 $1$ 结束度假的概率为 $7/9$（路径为 $1$，$1\to 2\to 3\to 4\to 5\to 1$，或 $1\to 5\to 4\to 3\to 2\to 1$），在 $2$ 结束度假的概率为 $2/9$。

对于第二个测试用例，Bessie 在 $3$ 结束度假的概率为 $1/3$，在 $5$ 结束度假的概率为 $2/3$。

样例输入 3

1

11 13
2 3 4 5 6 7 8 9 10 11 12
1 2
1 3
2 3
2 4
4 5
2 5
4 8
5 9
2 6
6 7
2 7
6 10
5 11

样例输出 3

133332478 200000394 577778352 999999971 399999938 933333282 355555536 800000020 18 600000029 18

子任务

• 输入 4-5: $N\le 11$
• 输入 6-7: 不存在简单环。
• 输入 8-11: 没有岛屿位于多于一个简单环上。
• 输入 12-15: 没有岛屿位于多于 $5$ 个简单环上。
• 输入 16-19: 没有岛屿位于多于 $50$ 个简单环上。
• 输入 20-23: 无额外约束。