Problem: One day, Takahashi was given the following problem from Aoki:

* You are given a tree with N vertices and an integer K. The vertices are numbered 1 through N. The edges are represented by pairs of integers (a_i, b_i).
* For a set S of vertices in the tree, let f(S) be the minimum number of the vertices in a subtree of the given tree that contains all vertices in S.
* There are <image> ways to choose K vertices from the trees. For each of them, let S be the set of the chosen vertices, and find the sum of f(S) over all <image> ways.
* Since the answer may be extremely large, print it modulo 924844033(prime).



Since it was too easy for him, he decided to solve this problem for all K = 1,2,...,N.

Constraints

* 2 ≦ N ≦ 200,000
* 1 ≦ a_i, b_i ≦ N
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}


Output

Print N lines. The i-th line should contain the answer to the problem where K=i, modulo 924844033.

Examples

Input

3
1 2
2 3


Output

3
7
3


Input

4
1 2
1 3
1 4


Output

4
15
13
4


Input

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


Output

7
67
150
179
122
45
7

Solution (in CPP):

Solution:
#include <cstdio>
#include <algorithm>
const long long MOD = 924844033;
int N, head[200001], next[399999], to[399999], E, size[200001], fa[200001], q[200001], D[200001], L = 1;
long long A[524288], B[524288], _B[200001];
long long POWER(long long a, long long b)
{
	long long r = 1;
	for (; b; b >>= 1)
	{
		if (b & 1)
			r = r * a % MOD;
		a = a * a % MOD;
	}
	return r;
}
void FFT(long long *a, int f = 1)
{
	static int p[524288];
	for (int i = 1; i < L; i++)
		p[i] = i & 1 ? p[i - 1] | L >> 1 : p[i >> 1] >> 1;
	for (int i = 0; i < L; i++)
		if (i < p[i])
			std::swap(a[i], a[p[i]]);
	for (int i = 1; i < L; i <<= 1)
	{
		long long w, wn = POWER(5, (MOD - 1) / 2 / i), x, y;
		if (f == -1)
			wn = POWER(wn, MOD - 2);
		for (int j = 0; j < L; j += i + i)
		{
			w = 1;
			for (int k = j; k < j + i; k++)
			{
				x = a[k];
				y = a[k + i] * w % MOD;
				a[k] = x + y < MOD ? x + y : x + y - MOD;
				a[k + i] = x - y < 0 ? x - y + MOD : x - y;
				w = w * wn % MOD;
			}
		}
	}
	if (f == -1)
	{
		long long D = POWER(L, MOD - 2);
		for (int i = 0; i < L; i++)
			a[i] = a[i] * D % MOD;
	}
}
int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v; i < N; i++)
	{
		scanf("%d%d", &u, &v);
		next[++E] = head[u], to[E] = v, head[u] = E;
		next[++E] = head[v], to[E] = u, head[v] = E;
	}
	int H = 0, T = 1, u;
	q[1] = 1;
	while (H < T)
		for (int e = head[u = q[++H]]; e; e = next[e])
			if (to[e] != fa[u])
				fa[q[++T] = to[e]] = u;
	for (int i = 1; i <= N; i++)
		size[i] = 1;
	for (int i = N; i > 1; i--)
		size[fa[q[i]]] += size[q[i]];
	A[0] = B[0] = B[1] = 1;
	for (int i = 2; i <= N; i++)
		B[i] = (MOD - MOD / i) * B[MOD % i] % MOD;
	for (int i = 1; i <= N; i++)
	{
		A[i] = A[i - 1] * i % MOD;
		B[i] = B[i - 1] * B[i] % MOD;
	}
	D[N] = N;
	for (int i = 2; i <= N; i++)
	{
		D[N - size[i]]--;
		D[size[i]]--;
	}
	for (int i = 1; i <= N; i++)
		A[i] = A[i] * (MOD + D[i]) % MOD;
	std::reverse(B, B + N + 1);
	std::copy(B, B + N + 1, _B);
	while (L <= N + N)
		L <<= 1;
	FFT(A);
	FFT(B);
	for (int i = 0; i < L; i++)
		A[i] = A[i] * B[i] % MOD;
	FFT(A, -1);
	for (int i = 1; i <= N; i++)
		printf("%lld\n", A[N + i] * _B[N - i] % MOD);
	return 0;
}