F. Magicology
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
I've always loved the word magic. It has a way of making people happy, of putting a smile on their faces.
— Anisphia Wynn Palettia

To push magicology toward a more rigorous discipline, Anisphia and Euphyllia build a mana circuit network at the detached palace. The network forms a tree$$$^{\text{∗}}$$$ with $$$n$$$ vertices labeled $$$1, 2, \cdots, n$$$, and vertex $$$i$$$ stores a mana value $$$a_i$$$.

Root the tree at vertex $$$1$$$. For a vertex $$$u$$$, let $$$\mathrm{Subtree}\left(u\right)$$$ be the set of vertices in the subtree of $$$u$$$ (including $$$u$$$ itself and all of its descendants$$$^{\text{†}}$$$).

Define one operation $$$f$$$ on an array $$$x = \left(x_1, x_2, \cdots, x_n\right)$$$ by $$$y = f\left(x\right)$$$, where $$$$$$ y_u = \sum_{v \in \mathrm{Subtree}\left(u\right)} x_v $$$$$$

They apply the operation exactly $$$k$$$ times: let $$$x^{\left(0\right)} = a$$$, and $$$x^{\left(t\right)} = f\left(x^{\left(t - 1\right)}\right)$$$ for all $$$1 \leq t \leq k$$$.

Output $$$x^{\left(k\right)}_1, x^{\left(k\right)}_2, \cdots, x^{\left(k\right)}_n$$$ modulo $$$998244353$$$.

$$$^{\text{∗}}$$$A tree with $$$n$$$ vertices is an undirected connected graph with $$$n$$$ vertices and $$$n-1$$$ edges. A rooted tree is a tree in which one of the vertices is special and is called the root.

$$$^{\text{†}}$$$The descendants of vertex $$$u$$$ are all vertices $$$v$$$ such that $$$v \neq u$$$ and on the shortest path from the root to $$$v$$$, vertex $$$u$$$ is encountered.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n, k$$$ ($$$1 \le n \le 5000$$$, $$$0 \le k \le 10^{18}$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ ($$$0 \le a_i \lt 998244353$$$).

The next $$$n - 1$$$ lines of each test case contain two integers $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$) — two vertices that the $$$i$$$-th edge of the tree connects.

It is guaranteed that the given edges form a tree, and it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, print $$$n$$$ integers $$$x^{\left(k\right)}_1, x^{\left(k\right)}_2, \cdots, x^{\left(k\right)}_n$$$ in one line, each taken modulo $$$998244353$$$.

Example
Input
3
5 2
1 2 3 4 5
1 3
3 4
3 5
1 2
6 1000000000000000000
3 1 4 1 5 9
1 2
2 3
2 4
4 5
4 6
3 1
10 20 30
1 2
3 2
Output
38 2 21 4 5
408356129 643450937 4 42549043 5 9
60 50 30
Note

In the first test case, $$$a = [1, 2, 3, 4, 5]$$$, so $$$$$$ x^{\left(0\right)} = a = [1, 2, 3, 4, 5] $$$$$$ $$$$$$ x^{\left(1\right)} = f\left(x^{\left(0\right)}\right) = [x^{\left(0\right)}_1 + x^{\left(0\right)}_2 + x^{\left(0\right)}_3 + x^{\left(0\right)}_4 + x^{\left(0\right)}_5, x^{\left(0\right)}_2, x^{\left(0\right)}_3 + x^{\left(0\right)}_4 + x^{\left(0\right)}_5, x^{\left(0\right)}_4, x^{\left(0\right)}_5] = [15, 2, 12, 4, 5] $$$$$$ $$$$$$ x^{\left(2\right)} = f\left(x^{\left(1\right)}\right) = [x^{\left(1\right)}_1 + x^{\left(1\right)}_2 + x^{\left(1\right)}_3 + x^{\left(1\right)}_4 + x^{\left(1\right)}_5, x^{\left(1\right)}_2, x^{\left(1\right)}_3 + x^{\left(1\right)}_4 + x^{\left(1\right)}_5, x^{\left(1\right)}_4, x^{\left(1\right)}_5] = [38, 2, 21, 4, 5] $$$$$$