```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e6;
const int mod=998244353;
const int INV=499122177;
int n,m,lim,F[N],G[N],tr[N],c[N],a[N],b[N],d[N],h[N];
int power(int a,int b,int p){
int ans=1;
while(b){
if(b&1) ans=(ans*a)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
const int g=3;
const int invg=power(g,mod-2,mod);
void ntt(int *f,int flag,int lim){
for(int i=0;i<=lim;i++) if(i<tr[i]) swap(f[i],f[tr[i]]);
for(int p=2;p<=lim;p<<=1){
int len=p>>1;
int tG=power((flag==1)?g:invg,(mod-1)/p,mod);
for(int k=0;k<=lim;k+=p){
int buf=1;
for(int l=k;l<k+len;l++){
int tt=buf*f[l+len]%mod;
f[l+len]=f[l]-tt;
if(f[l+len]<0) f[l+len]+=mod;
f[l]=f[l]+tt;
if(f[l]>mod) f[l]-=mod;
buf=buf*tG%mod;
}
}
}
if(!flag){
int invn=power(lim,mod-2,mod);
for(int i=0;i<=lim;i++){
f[i]=f[i]%mod*invn%mod;
}
}
}
void times(int *f,int *g,int *sav,int lim){
// int invn=power(lim,mod-2,mod);
ntt(f,1,lim),ntt(g,1,lim);
for(int i=0;i<=lim;i++) sav[i]=f[i]*g[i]%mod;
ntt(sav,0,lim);
// for(int i=0;i<=lim;i++) sav[i]=sav[i]*power(lim,mod-2,mod)%mod;
}void polyinv(int *a,int *b,int len){
if(len==1){
b[0]=power(a[0],mod-2,mod);
return;
}
polyinv(a,b,(len+1)>>1);
int lim=1;
while(lim<=len+len) lim<<=1;
for(int i=1;i<=lim;i++){
tr[i]=(tr[i>>1]>>1)|((i&1)?lim>>1:0);
}
for(int i=0;i<len;i++){
c[i]=a[i];
}
for(int i=len;i<lim;i++) c[i]=0;
ntt(c,1,lim),ntt(b,1,lim);
for(int i=0;i<lim;i++){
b[i]=(2-c[i]*b[i]%mod+mod)%mod*b[i]%mod;;
}
ntt(b,0,lim);
for(int i=len;i<lim;i++){
b[i]=0;
}
}
void getsqrt(int *f,int *g,int len){
if(len==1){
g[0]=1;
return;
}
getsqrt(f,g,(len+1)>>1);
//getsqrt(f,g,len>>1);
memset(d,0,len*4);
memset(a,0,len*4);
memset(c,0,len*4);
polyinv(f,d,len);
for(int i=0;i<len;i++){
a[i]=f[i];
}
int lim=1,L=0;
while(lim<=len+len) lim<<=1,L++;
for(int i=0;i<=lim;i++){
tr[i]=(tr[i>>1]>>1)|((i&1)?(1<<(L-1)):0);
}
times(a,d,h,lim);
for(int i=0;i<len;i++){
g[i]=(g[i]+h[i])%mod*INV%mod;
}
}
signed main(){
scanf("%lld",&n);
for(int i=0;i<n;i++){
scanf("%lld",&F[i]);
}
getsqrt(F,G,n);
for(int i=0;i<n;i++){
printf("%lld ",G[i]);
}
return 0;
}
```
by KanadeLing @ 2021-04-03 20:12:51