Il y a $n$ villes à Saint Waterloo. Elles sont reliées par $n - 1$ lignes aériennes non orientées, de telle sorte qu'il est possible de se rendre de n'importe quelle ville à n'importe quelle autre ville en utilisant ces lignes.

Disons que deux villes entretiennent une bonne relation s'il est possible de passer de l'une à l'autre en utilisant au plus $x$ vols.

De plus, disons qu'un ensemble de $k$ villes est amical si toutes les paires de villes qu'il contient entretiennent une bonne relation. Vous devez trouver le nombre d'ensembles de villes amicaux pour chaque $k$, tel que $1 \le k \le n$. Comme ces valeurs peuvent être très grandes, calculez-les modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient deux entiers $n, x$ ($1 \le n \le 300\,000$, $0 \le x \le n - 1$) : le nombre de villes à Saint Waterloo et $x$.

Les $n - 1$ lignes suivantes contiennent les descriptions des arêtes, de telle sorte que la $i$-ième ligne contient deux entiers $a, b$ ($1 \le a, b \le n$), les indices des villes reliées par la $i$-ième ligne aérienne.

Sortie

Affichez $n$ entiers : le nombre d'ensembles amicaux de $1, 2, \dots, n$ villes, modulo $998\,244\,353$.

Exemples

Entrée 1

1 0

Sortie 1

1

Entrée 2

5 1
1 2
2 3
3 4
4 5

Sortie 2

5 4 0 0 0

Entrée 3

4 2
1 2
1 3
1 4

Sortie 3

4 6 4 1

Remarque

Dans le deuxième exemple, tous les ensembles amicaux possibles sont de taille 1 et 2, et le nombre d'ensembles amicaux pour ces tailles correspond respectivement au nombre de villes et au nombre de lignes aériennes.

Dans le troisième exemple, il est possible de se rendre de n'importe quelle ville à n'importe quelle autre ville en utilisant au plus $x$ vols, donc le nombre d'ensembles amicaux de $k$ villes est $\binom{4}{k}$.