Given a tree with $n$ vertices, the color of vertex $i$ is $c[i]~(1\leq c[i]\leq n)$.

The virtual tree $T(S)$ of a set of vertices $S$ is defined as the set of all vertices $x$ that satisfy at least one of the following two conditions:

1. $x \in S$
2. After removing $x$ and its incident edges, there exists at least one pair of vertices in $S$ that are no longer connected.

Let $G(i)$ be the set of all vertices with color $i$.

You need to calculate the number of arrays $a[1..k]$ of length $k$ that satisfy the following conditions:

1. For $1\leq i \leq k-1$, $a[i] < a[i+1]$.
2. There exists at least one vertex $x$ such that for all $i\in [1,k]$, $x \in T(G(a[i]))$.

Given a parameter $m$, let $f(k)$ be the number of such arrays of length $k$. You need to output the values of $f(1), \dots, f(m)$. Since the answers can be very large, output them modulo $998244353$.

Input

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, representing $c[1 \dots n]$.

The next $n-1$ lines each contain two integers $(u, v)$, representing an undirected edge $(u, v)$.

It is guaranteed that the input is a tree.

Output

Output $m$ lines, where the $i$-th line contains the value of $f(i)$ modulo $998244353$.

Examples

Input 1

3 3
1 2 1
1 2
2 3

Output 1

2
1
0

Subtasks

Task 1 (12pts): $1\leq n\leq 100$

Task 2 (41pts): $m=2$

Task 3 (14pts): $1\leq m\leq 1000$

Task 4 (16pts): For all edges $(a, b)$, $|a-b|=1$

Task 5 (17pts): No additional constraints

For all data, $1\leq m\leq n\leq 10^5$ and $1\leq c[i]\leq n$.