Có $n$ thành phố tại Saint Waterloo. Chúng được kết nối với nhau bởi $n - 1$ đường bay vô hướng, sao cho có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách sử dụng các đường bay.

Ta nói rằng hai thành phố có mối quan hệ tốt nếu có thể đi từ thành phố này đến thành phố kia bằng cách sử dụng tối đa $x$ chuyến bay.

Ngoài ra, ta nói rằng một tập hợp gồm $k$ thành phố là thân thiện nếu mọi cặp thành phố trong tập hợp đó đều có mối quan hệ tốt với nhau.

Bạn cần tìm số lượng tập hợp thành phố thân thiện cho mỗi $k$, với $1 \le k \le n$. Vì các giá trị này có thể rất lớn, hãy tìm chúng theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n, x$ ($1 \le n \le 300\,000, 0 \le x \le n - 1$): số lượng thành phố tại Saint Waterloo và $x$.

$n - 1$ dòng tiếp theo chứa mô tả các cạnh, trong đó dòng thứ $i$ chứa hai số nguyên $a, b$ ($1 \le a, b \le n$), là chỉ số của các thành phố được kết nối bởi đường bay thứ $i$.

Dữ liệu ra

In ra $n$ số nguyên: số lượng tập hợp thân thiện gồm $1, 2, \dots, n$ thành phố, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

1 0

Dữ liệu ra 1

1

Dữ liệu vào 2

5 1
1 2
2 3
3 4
4 5

Dữ liệu ra 2

5 4 0 0 0

Dữ liệu vào 3

4 2
1 2
1 3
1 4

Dữ liệu ra 3

4 6 4 1

Ghi chú

Trong ví dụ thứ hai, tất cả các tập hợp thân thiện có thể có đều có kích thước 1 và 2, và số lượng tập hợp thân thiện cho các kích thước này lần lượt là số lượng thành phố và số lượng đường bay.

Trong ví dụ thứ ba, có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác bằng cách sử dụng tối đa $x$ chuyến bay, vì vậy số lượng tập hợp thân thiện gồm $k$ thành phố là $\binom{4}{k}$.