Gojo possède un arbre à $n$ sommets. Il a appris la technique de compression du territoire (domain compression), qui fonctionne comme suit :

• Tout d'abord, il choisit un certain sommet $v$ qui n'a pas encore été supprimé du graphe. Ensuite, pour chaque paire de sommets $u < w$ reliés à $v$, il ajoute une arête non orientée $(u, w)$ si elle n'était pas déjà présente dans le graphe. Après cela, il efface $v$ du graphe ainsi que toutes les arêtes qui lui sont incidentes.

Pour chaque $k$ ($1 \le k \le n$), il s'intéresse au nombre total d'arêtes dans les graphes restants sur l'ensemble des $\frac{n!}{(n-k)!}$ façons d'effectuer les opérations. Comme les réponses peuvent être très grandes, affichez-les modulo $998\,244\,353$.

Entrée

La première ligne contient un entier $n$ ($2 \le n \le 10^5$) — le nombre de sommets de l'arbre.

Ensuite, $n - 1$ lignes contiennent des paires d'entiers $u_i, v_i$ ($1 \le u_i, v_i \le n$) — la description des arêtes de l'arbre.

Sortie

Affichez $n$ entiers — le nombre total d'arêtes pour chaque $k$ modulo $998\,244\,353$.

Exemples

Entrée 1

5
1 2
2 3
3 5
3 4

Sortie 1

16 44 60 0 0

Entrée 2

8
1 2
2 3
2 4
4 5
4 7
7 8
6 7

Sortie 2

51 316 1596 6120 15720 20160 0 0