Saint Waterloo には $n$ 個の都市があり、$n-1$ 本の無向の航空路線で結ばれており、どの都市からどの都市へも航空路線を使って移動できる。

2 つの都市間において、高々 $x$ 回のフライトで一方から他方へ移動できるとき、それらの都市は「良好な関係」にあると言う。

さらに、$k$ 個の都市からなる集合において、その集合内のすべての都市のペアが良好な関係にあるとき、その集合を「フレンドリー」であると言う。

$1 \le k \le n$ のそれぞれについて、フレンドリーな都市の集合の数を求めよ。これらの値は非常に大きくなる可能性があるため、それぞれ $998\,244\,353$ で割った余りを求めよ。

入力

入力の最初の行には、2 つの整数 $n, x$ ($1 \le n \le 300\,000, 0 \le x \le n - 1$) が含まれる。これは Saint Waterloo の都市の数と $x$ を表す。

続く $n-1$ 行には辺の記述が含まれ、$i$ 番目の行には $i$ 番目の航空路線で結ばれた都市のインデックスを表す 2 つの整数 $a, b$ ($1 \le a, b \le n$) が含まれる。

出力

$n$ 個の整数を出力せよ。これらはそれぞれ $1, 2, \dots, n$ 個の都市からなるフレンドリーな集合の数であり、$998\,244\,353$ を法とする値である。

入出力例

入力 1

1 0

出力 1

1

入力 2

5 1
1 2
2 3
3 4
4 5

出力 2

5 4 0 0 0

入力 3

4 2
1 2
1 3
1 4

出力 3

4 6 4 1

注記

2 番目の例では、考えられるすべてのフレンドリーな集合はサイズが 1 または 2 であり、それぞれのサイズに対するフレンドリーな集合の数は、都市の数および航空路線の数と一致する。

3 番目の例では、どの都市からどの都市へも高々 $x$ 回のフライトで移動できるため、$k$ 個の都市からなるフレンドリーな集合の数は $\binom{4}{k}$ となる。