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>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 2E5 + 10, MAXL = 1 << 19;
const ll MOD = 924844033;

int n;
vector<int> E[MAXN];
int size[MAXN];
ll cnt[MAXN], c[MAXN];
ll A[MAXL], B[MAXL];

ll modExp(ll e, ll n, ll m = MOD){
	ll ret = 1;
	for (; n; n >>= 1, e = e * e % m)
		if (n & 1)
			ret = ret * e % m;
	return ret;
}

void DFS(int u, int pre){
	size[u] = 1;
	for (int v, i = 0; i < E[u].size(); ++i){
		if ((v = E[u][i]) == pre)
			continue;
		DFS(v, u);
		++cnt[size[v]];
		++cnt[n - size[v]];
		size[u] += size[v];
	}
}

typedef long long LL;
LL pm(LL a,LL n,LL m){
    LL r=1;
    for(;n;n>>=1,a=a*a%m)
        if(n&1)r=r*a%m;
    return r;
}

const LL P=924844033,g=5;
void ntt(LL *a,size_t n,bool inv=false){
    LL w=1,d=pm(g,(P-1)/n,P),t;
    size_t i,j,c,s;
    if(inv){
        for(i=1,j=n-1;i<j;swap(a[i++],a[j--]));
        for(t=pm(n,P-2,P),i=0;i<n;++i)a[i]=a[i]*t%P;
    }
    for(s=n>>1;s;s>>=w=1,d=d*d%P)
    for(c=0;c<s;++c,w=w*d%P)
    for(i=c;i<n;i+=s<<1){
        a[i|s]=(a[i]+P-(t=a[i|s]))*w%P;
        a[i]=(a[i]+t)%P;
    }
    for(i=1;i<n;++i){
        for(j=0,s=i,c=n>>1;c;c>>=1,s>>=1)j=j<<1|s&1;
        if(i<j)swap(a[i],a[j]);
    }
}

int main(){
	scanf("%d", &n);
	for (int u, v, i = 1; i < n; ++i){
		scanf("%d%d", &u, &v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	DFS(1, 0);
	cnt[n] = MOD - n;
	ll e = 1;
	for (int i = 1; i <= n; ++i){
		e = e * i % MOD;
		A[i] = (MOD - cnt[i]) * e % MOD;
	}
	e = modExp(e, MOD - 2, MOD);
	for (int i = 0; i <= n; ++i){
		B[i] = c[n - i] = e;
		e = e * (n - i) % MOD;
	}

	int len = 1;
	for (; len < n * 2 + 2; len <<= 1);
	ntt(A, len), ntt(B, len);
	for (int i = 0; i < len; ++i)
		A[i] = A[i] * B[i] % MOD;
	ntt(A, len, true);
	for (int i = 1; i <= n; ++i)
		printf("%d\n", (int)(c[i] * A[n + i] % MOD));
	return 0;
}