给一个 $n$ 个点的树，第 $i$ 个点的颜色为 $c[i]~(1\leq c[i]\leq n)$

定义一个点集 $S$ 的虚树 $T(S)$ 为：所有满足以下两个条件中至少一个条件的点 $x$ 构成的集合：

1. $x \in S$
2. 去掉 $x$ 以及其相关的边后， $S$ 中至少有一对点不连通

定义 $G(i)$ 为所有颜色为 $i$ 的点构成的集合

你需要计算有几个长度为 $k$ 的数组 $a[1..k]$，满足以下所有条件：

1. 对于 $1\leq i \leq k-1$，有 $a[i] < a[i+1]$
2. 存在至少一个点 $x$，使得对于 $i\in [1,k]$，都有 $x \in T(G(a[i]))$

再给定一个参数 $m$，假设满足条件的长度为 $k$ 的数组一共有 $f(k)$ 个，你需要输出 $f(1)...f(m)$ 的值，由于答案可能很大，所以你只需要输出他们对 $998244353$ 取模后的值

输入格式

第一行两个整数 $n,m$

第二行 $n$ 个整数，表示 $c[1...n]$

接下来 $n-1$ 行，每行两个整数 $(u,v)$，表示一条无向边 $(u,v)$

保证给出的一定是一棵树

输出格式

输出 $m$ 行，第 $i$ 行一个整数表示 $f(i)$ 对 $998244353$ 取模后的值

样例数据

样例 1 输入

3 3
1 2 1
1 2
2 3

样例 1 输出

2
1
0

子任务

Task1 (12pts)：$1\leq n\leq 100$

Task2 (41pts)：$m=2$

Task3 (14pts)：$1\leq m\leq 1000$

Task4 (16pts)：对于所有的边 $(a,b)$，满足 $|a-b|=1$

Task5 (17pts)：无特殊限制

对于所有数据，有 $1\leq m\leq n\leq 10^5$，$1\leq c[i]\leq n$