#include <bits/stdc++.h> using namespace std; #pragma optimize(2) #define int long long #define pii pair<int,int> #define fi first #define se second #define mp make_pair const int maxn=1e6+10,mod=998244353; int n; int a[maxn]; int l[maxn],r[maxn]; int lg[maxn]; int inv[maxn]; int q_pow(int a,int b) { int ans=1; while(b) { if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } //struct SA //{ // int len; // int sa[maxn],rk[2*maxn]; // int cnt[maxn],height[maxn]; // int s[maxn]; // int st[maxn][30]; // struct node // { // int x,y; // int id; // }a[maxn],b[maxn]; // void build() // { // for(int i=1;i<=n;i++) cnt[i]=0; // for(int i=1;i<=n;i++) cnt[s[i]]=1; // for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; // for(int i=1;i<=n;i++) rk[i]=cnt[s[i]]; // for(int l=1;l<n;l*=2) // { // for(int i=1;i<=n;i++) a[i].x=rk[i],a[i].y=rk[i+l],a[i].id=i; // for(int i=1;i<=n;i++) cnt[i]=0; // for(int i=1;i<=n;i++) cnt[a[i].y]++; // for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; // for(int i=1;i<=n;i++) b[cnt[a[i].y]--]=a[i]; // for(int i=1;i<=n;i++) cnt[i]=0; // for(int i=1;i<=n;i++) cnt[a[i].x]++; // for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1]; // for(int i=n;i>=1;i--) a[cnt[b[i].x]--]=b[i]; // for(int i=1;i<=n;i++) // if(a[i].x==a[i-1].x&&a[i].y==a[i-1].y) rk[a[i].id]=rk[a[i-1].id]; // else rk[a[i].id]=rk[a[i-1].id]+1; // } // for(int i=1;i<=n;i++) sa[rk[i]]=i; // int p=0; // for(int i=1;i<=n;i++) // { // if(p>0) p--; // while(s[sa[rk[i]]+p]==s[sa[rk[i]-1]+p]) p++; // height[rk[i]]=p; // } // } // void buildST() // { // for(int i=1;i<=n;i++) st[i][0]=height[i]; // for(int j=1;j<=20;j++) for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=min(st[i][j-1],st[i+(1<<j)-1][j-1]); // } // int query(int x,int y) // { // if(x==y) return n-x+1; // int l=rk[x],r=rk[y]; // l++; // return min(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]); // } //}f1,f2; struct SA { int sa[maxn],rk[maxn],oldrk[maxn<<1],cnt[maxn],id[maxn],key1[maxn],h[maxn]; int ST[20][maxn],sz; bool cmp(int x,int y,int w) { return oldrk[x]==oldrk[y]&&oldrk[x+w]==oldrk[y+w]; } void build(int a[],int n) { int m=n,p=0;sz=n; for(int i=1;i<=n;i++) cnt[i]=0; for(int i=1;i<=n;i++)rk[i]=a[i],++cnt[rk[i]]; for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i; for(int w=1;;w<<=1,m=p) { p=0; for(int i=n;i>n-w;i--)id[++p]=i; for(int i=1;i<=n;i++)if(sa[i]>w)id[++p]=sa[i]-w; for(int i=0;i<=n;i++)cnt[i]=0; for(int i=1;i<=n;i++)++cnt[key1[i]=rk[id[i]]]; for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1]; for(int i=n;i>=1;i--)sa[cnt[key1[i]]--]=id[i]; for(int i=1;i<=n;i++)oldrk[i]=rk[i];p=0; for(int i=1;i<=n;i++)rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p; if(p==n){ for(int i=1;i<=n;i++)sa[rk[i]]=i; break; } } for(int i=1,k=0;i<=n;i++) { if(k>0)k--; while(a[i+k]==a[sa[rk[i]-1]+k])++k; h[rk[i]-1]=k; } for(int i=1;i<n;i++)ST[0][i]=h[i]; for(int i=1;i<20;i++) for(int j=1;j+(1<<i)-1<n;j++) ST[i][j]=min(ST[i-1][j],ST[i-1][j+(1<<(i-1))]); } int query(int i,int j) { if(i==j)return n-i+1; int l=rk[i],r=rk[j];if(l>r)swap(l,r);r--; int k=lg[r-l+1]; return min(ST[k][l],ST[k][r-(1<<k)+1]); } void clear() { for(int i=0;i<=sz;i++)sa[i]=rk[i]=cnt[i]=id[i]=key1[i]=h[i]=0; for(int i=0;i<=sz*2;i++)oldrk[i]=0; for(int i=0;i<21;i++)for(int j=1;j<=sz;j++)ST[i][j]=0; } }f1,f2; int ans; struct dsu { int root[maxn],llim[maxn],rlim[maxn]; void init() { for(int i=1;i<=n;i++) root[i]=i,llim[i]=l[i],rlim[i]=r[i]; } int getroot(int x) { assert(x!=0); if(root[x]==x) return x; return root[x]=getroot(root[x]); } void merge(int u,int v) { int tu=getroot(u),tv=getroot(v); if(tu==tv) return ; root[tu]=tv; if(ans!=0) { assert(rlim[tu]-llim[tu]+1>=0); ans=ans*inv[rlim[tu]-llim[tu]+1]%mod*inv[rlim[tv]-llim[tv]+1]%mod; } llim[tv]=max(llim[tv],llim[tu]); rlim[tv]=min(rlim[tv],rlim[tu]); ans=ans*max(0ll,rlim[tv]-llim[tv]+1)%mod; } }t; struct dsu2 { int root[maxn]; void init() { for(int i=1;i<=n;i++) root[i]=i; } int getroot(int x) { assert(x!=0); if(root[x]==x) return x; return root[x]=getroot(root[x]); } }seg[20]; void merge(int l,int r,int pos) { assert(l<=n&&r<=n); if(pos<0) return ; int tl=seg[pos].getroot(l),tr=seg[pos].getroot(r); if(tl==tr) return ; seg[pos].root[tl]=tr; if(pos==0) { t.merge(l,r); return ; } merge(l,r,pos-1); merge(l+(1<<(pos-1)),r+(1<<(pos-1)),pos-1); } signed main() { // freopen("yoimiya.in","r",stdin); // freopen("yoimiya.out","w",stdout); ios::sync_with_stdio(false); int T; cin>>T; for(int i=2;i<=1e6;i++) lg[i]=lg[i/2]+1; inv[0]=1; for(int i=1;i<=1e6;i++) inv[i]=q_pow(i,mod-2); while(T--) { ans=1; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) cin>>l[i]>>r[i],ans=ans*(r[i]-l[i]+1)%mod; t.init(); for(int i=0;i<=19;i++) seg[i].init(); f1.build(a,n),reverse(a+1,a+1+n); f2.build(a,n),reverse(a+1,a+1+n); int pos=n/2+1; for(int len=1;len<=n/2;len++) { for(int i=1;len*i+len<=n;i++) { int pos=i*len; if(a[pos]!=a[pos+len]) continue; int llen=f2.query(n-pos+1,n-(pos+len)+1),rlen=f1.query(pos,pos+len); if(llen+rlen-1<len) continue; int l=pos-llen+1,r=pos+rlen-1; merge(l,l+len,lg[r-l+1]); merge(r-(1<<lg[r-l+1])+1,r+len-(1<<lg[r-l+1])+1,lg[r-l+1]); } cout<<ans<<" "; if(ans==0) { pos=len; break; } } for(int i=pos+1;i<=n/2;i++) cout<<0<<" "; cout<<endl; f1.clear(),f2.clear(); } return 0; }