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<bits/stdc++.h>
#define mo 924844033ll
using namespace std;
long long a[800010],b[800010],c[800010],ym[800010],fac[200010],nifac[200010];
vector<int> des[200010];
int n;
int getmi(int a,int x)
{
	int ans=1;
	while (x)
	{
		if (x&1) ans=(long long)ans*a%mo;
		a=(long long)a*a%mo;
		x>>=1;
	}
	return ans;
}
long long C(int n,int m)
{
	if ((n<0)||(m<0)||(n<m)) return 0;
	return (long long)fac[n]*nifac[m]%mo*nifac[n-m]%mo;
}
int dfs(int s,int pre=0)
{
	int ans=1;
	for (int k=0;k<des[s].size();k++) if (des[s][k]!=pre) ans+=dfs(des[s][k],s);
	if (pre) {a[ans]++;a[n-ans]++;}
	return ans;
}
void fft(long long a[],int n)
{
	if (n==1) return;
	long long l[n>>1],r[n>>1];
	for (int i=0;i<(n>>1);i++)
	{
		l[i]=a[i<<1];
		r[i]=a[(i<<1)+1];
	}
	fft(l,n>>1);fft(r,n>>1);
	long long wn=ym[n],w=1;
	for (int i=0;i<(n>>1);i++)
	{
		a[i]=(l[i]+w*r[i])%mo;
		a[i+(n>>1)]=(l[i]-w*r[i])%mo;
		w=w*wn%mo;
	}
}
int main()
{
	scanf("%d",&n);
	fac[0]=nifac[0]=1;
	for (int i=1;i<=n;i++)
	{
		fac[i]=(long long)fac[i-1]*i%mo;
		nifac[i]=getmi(fac[i],mo-2);
	}
	if (fac[n]*nifac[n]%mo!=1) assert(0);
	for (int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		des[u].push_back(v);des[v].push_back(u);
	}
	dfs(1);
	for (int i=0;i<=n;i++)
	{
		a[i]=(long long)a[i]*fac[i]%mo;
		c[i]=nifac[n-i];
	}
	//for (int i=0;i<=2*n;i++) cout<<i<<' '<<a[i]<<' '<<c[i]<<endl;
	/*for (int i=0;i<=n;i++)
	for (int j=0;j<=2*n;j++)
		b[i+j]=(b[i+j]+a[i]*c[j])%mo;*/
	//for (int i=0;i<=3*n;i++) cout<<i<<' '<<b[i]<<endl;
	//for (int i=1;i<=n;i++) printf("%lld\n",(mo-b[i+n]*nifac[i]%mo+n*C(n-1,i-1)+n*C(n-1,i))%mo);
	
	int mi=1;while (mi<=2*n+10) mi<<=1;
	for (int i=1;i<=mi;i<<=1) ym[i]=getmi(5,(mo-1)/i);
	fft(a,mi);fft(c,mi);
	for (int i=0;i<mi;i++) a[i]=a[i]*c[i]%mo;
	fft(a,mi);
	for (int i=1;i<(mi>>1);i++) swap(a[i],a[mi-i]);
	int ni=getmi(mi,mo-2);
	for (int i=0;i<mi;i++) a[i]=a[i]*ni%mo;
	for (int i=0;i<mi;i++) a[i]+=mo;
	//for (int i=0;i<=n;i++) cout<<a[i+n]*nifac[i]%mo<<endl;
	for (int i=1;i<=n;i++) printf("%lld\n",(mo-a[i+n]*nifac[i]%mo+n*C(n-1,i-1)+n*C(n-1,i))%mo);
	/*for (int i=1;i<=n;i++)
	{
		int ans=(n*C(n-1,i-1)+n*C(n-1,i))%mo;
		for (int j=0;j<=n;j++)
		{
			ans-=(a[j]+b[j])*C(j,i);
		}
		cout<<(ans%mo+mo)%mo<<endl;
	}*/
}