Gojo has a tree with $n$ vertices. He learned the technique of domain compression, which works as follows:

• First, he chooses some vertex $v$ which was not previously deleted from the graph. Next, for each pair of vertices $u < w$ which are connected to $v$, he adds an undirected edge $(u, w)$ if it was not previously contained in the graph. After that, he erases $v$ from the graph with all the edges incident to it.

For each $k$ ($1 \le k \le n$), he is interested in the total number of edges in the remaining graphs for all $\frac{n!}{(n-k)!}$ ways to perform the operations. Since the answers can be very large, output them modulo $998\,244\,353$.

Input

The first line contains an integer $n$ ($2 \le n \le 10^5$) — the number of vertices in the tree.

Next, $n - 1$ lines contain pairs of integers $u_i, v_i$ ($1 \le u_i, v_i \le n$) — the description of the edges of the tree.

Output

Output $n$ integers — the total number of edges for each $k$ modulo $998\,244\,353$.

Examples

Input 1

5
1 2
2 3
3 5
3 4

Output 1

16 44 60 0 0

Input 2

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

Output 2

51 316 1596 6120 15720 20160 0 0