У Годжо есть дерево на $n$ вершинах. Он освоил технику сжатия территории, которая работает следующим образом:

• Сначала он выбирает некоторую вершину $v$, которая ранее не была удалена из графа. Затем для каждой пары вершин $u < w$, соединённых с $v$, он добавляет неориентированное ребро $(u, w)$, если оно ранее не содержалось в графе. После этого он удаляет вершину $v$ из графа вместе со всеми инцидентными ей рёбрами.

Для каждого $k$ ($1 \le k \le n$) его интересует суммарное количество рёбер в оставшихся графах по всем $\frac{n!}{(n-k)!}$ способам выполнить операции. Поскольку ответы могут быть очень большими, выведите их по модулю $998\,244\,353$.

Входные данные

Первая строка содержит целое число $n$ ($2 \le n \le 10^5$) — количество вершин в дереве.

Следующие $n - 1$ строк содержат пары целых чисел $u_i, v_i$ ($1 \le u_i, v_i \le n$) — описание рёбер дерева.

Выходные данные

Выведите $n$ целых чисел — суммарное количество рёбер для каждого $k$ по модулю $998\,244\,353$.

Примеры

Входные данные 1

5
1 2
2 3
3 5
3 4

Выходные данные 1

16 44 60 0 0

Входные данные 2

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

Выходные данные 2

51 316 1596 6120 15720 20160 0 0