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 pb push_back

using namespace std;
typedef long long ll;

const int N=200005,M=262205,P=(441<<21)+1,g=5,K=10000005;

int memory[K],*pointer=memory;
inline int lset(int n){int l=1;while(l<n)l<<=1;return l;}
inline int *getarr(int l){int*ret=pointer;pointer+=l;return ret;}

int *sum[M<<1],*mul[M<<1],_w[20][M];
int n,sz[N],cnt[N];
vector<int>e[N];

inline int fpow(int a,int t){
	static int r;
	for(r=1;t;a=(ll)a*a%P,t>>=1)if(t&1)r=(ll)r*a%P;
	return r;
}

void predo(int n){
	n++;n=lset(n);
	int l=2,p=1,w;
	while(l<=n){
		w=fpow(g,(P-1)/l);
		int*f=_w[p];f[0]=1;
		for(int j=1;j<(l>>1);j++)f[j]=(ll)f[j-1]*w%P;
		l<<=1,p++;
	}
}

void ntt(int*a,int n,int d){
	int i,j=n>>1,k,t=0,l,u,v,*p;
	for(i=1;i<n-1;i++){
		if(i<j)swap(a[i],a[j]);
		for(k=n>>1;(j^=k)<k;k>>=1);
	}
	for(l=2;l<=n;l<<=1){
		i=l>>1,p=_w[++t];
		for(j=0;j<n;j+=l)for(k=0;k<i;k++){
			u=a[j+k],v=(ll)a[j+k+i]*p[k]%P;
			a[j+k]=(u+v)%P,a[j+k+i]=(u-v+P)%P;
		}
	}
	if(d==-1){
		for(i=0,v=fpow(n,P-2);i<n;i++)a[i]=(ll)a[i]*v%P;
		for(i=1;i<n/2;i++)swap(a[i],a[n-i]);
	}
}

void conv(int*a,int na,int*b,int nb,int*r,int n){
	static int ta[M],tb[M],tc[M];
	na++,nb++,n++;int m=lset(n);
	memset(ta,0,m<<2),memset(tb,0,m<<2),memcpy(ta,a,na<<2),memcpy(tb,b,nb<<2);
	ntt(ta,m,1),ntt(tb,m,1);
	for(int i=0;i<m;i++)tc[i]=(ll)ta[i]*tb[i]%P;
	ntt(tc,m,-1);
	memcpy(r,tc,n<<2);
}

void check(int x,int l,int r){
	if(l==r){
		sum[x]=getarr(2),mul[x]=getarr(2);
		sum[x][0]=sum[x][1]=cnt[l],mul[x][0]=mul[x][1]=1;
		return;
	}
	int ls=x<<1,rs=ls|1,mid=(l+r)>>1,dl=mid-l+1,dr=r-mid,dn=r-l+1;
	check(ls,l,mid),check(rs,mid+1,r);
	sum[x]=getarr(dn+1),mul[x]=getarr(dn+1);
	conv(mul[ls],dl,mul[rs],dr,mul[x],dn);
	conv(mul[ls],dl,sum[rs],dr,sum[x],dn);
	for(int i=0;i<=dl;i++)(sum[x][i]+=sum[ls][i])%=P;
}

void dfs(int x,int fa){sz[x]=1;for(int v:e[x])if(v!=fa)dfs(v,x),sz[x]+=sz[v];}

int main(){
	scanf("%d",&n);
	predo(n);
	for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),e[u].pb(v),e[v].pb(u);
	dfs(1,0);
	for(int i=2;i<=n;i++)cnt[sz[i]]--,cnt[n-sz[i]]--;
	cnt[n]+=n;
	for(int i=1;i<=n;i++)if(cnt[i]<0)cnt[i]+=P;
	check(1,1,n);
	for(int k=1;k<=n;k++)printf("%d\n",sum[1][k]);
	return 0;
}