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>
typedef long long ll;
const int MaxN=1<<18,mod=924844033;
int sz[MaxN];
struct edge{int to;edge*next;}E[MaxN*2],*ne=E,*fir[MaxN];
void link(int u,int v){*ne=(edge){v,fir[u]};fir[u]=ne++;}
void dfs(int i,int f=0){
	sz[i]=1;
	for(edge*e=fir[i];e;e=e->next)
		if(e->to!=f)dfs(e->to,i),sz[i]+=sz[e->to];
}
ll fac[MaxN],ifac[MaxN],w[MaxN*2];
int A[MaxN*2],B[MaxN*2];
ll pw(ll a,ll n=mod-2){ll b=1;for(;n;n>>=1)n%2?b=b*a%mod:1,a=a*a%mod;return b;}
void dft(int*a,int n,bool r=0){
	*w=1;w[1]=pw(5,(mod-1)/n);
	if(r)w[1]=pw(w[1]);
	for(int i=2;i<n;i++)w[i]=w[i-1]*w[1]%mod;
	for(int i=0,j=0,t;i<n;i++){
		if(i<j)t=a[i],a[i]=a[j],a[j]=t;
		for(t=n/2;(j^=t)<t;t/=2);
	}
	for(int i=1,m=1;m<n;i++,m*=2){
		for(int j=0;j<n;j+=m<<1){
			for(int k=0,t;k<m;k++){
				t=a[j+m+k]*w[(n>>i)*k]%mod;
				a[j+m+k]=(a[j+k]+mod-t)%mod;
				(a[j+k]+=t)%=mod;
			}
		}
	}
	if(r){
		ll I=pw(n);
		for(int i=0;i<n;i++)a[i]=a[i]*I%mod;
	}
}
int main(){
	int N;scanf("%d",&N);
	for(int i=1,u,v;i<N;i++)scanf("%d%d",&u,&v),link(u,v),link(v,u);
	dfs(1);
	for(int i=*fac=1;i<=N;i++)fac[i]=fac[i-1]*i%mod;
	ifac[N]=pw(fac[N]);
	for(int i=N;i;i--)ifac[i-1]=ifac[i]*i%mod;
	for(int i=2;i<=N;i++)A[sz[i]]++,A[N-sz[i]]++;
	for(int i=0;i<=N;i++){
		A[i]=A[i]*fac[N-i]%mod;
		B[i]=ifac[i]%mod;
	}
	int n=1;while(n<=N*2)n*=2;
	dft(A,n);
	dft(B,n);
	for(int i=0;i<n;i++)A[i]=1ll*A[i]*B[i]%mod;
	dft(A,n,1);
	for(int i=1;i<=N;i++){
		int ans=(fac[N]*ifac[N-i]%mod*N%mod+mod-A[N-i])*ifac[i]%mod;
		printf("%d\n",ans);
	}
}