from sys import stdin input=lambda :stdin.readline()[:-1] class segtree(): def __init__(self,init,func,ide): self.n=len(init) self.func=func self.ide=ide self.size=1<<(self.n-1).bit_length() self.tree=[self.ide for i in range(2*self.size)] for i in range(self.n): self.tree[self.size+i]=init[i] for i in range(self.size-1,0,-1): self.tree[i]=self.func(self.tree[2*i], self.tree[2*i|1]) def update(self,k,x): k+=self.size self.tree[k]=x k>>=1 while k: self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1]) k>>=1 def get(self,i): return self.tree[i+self.size] def add(self,k,x): x+=self.get(k) self.update(k,x) def query(self,l,r): l+=self.size r+=self.size l_res=self.ide r_res=self.ide while l>=1 r>>=1 return self.func(l_res,r_res) def debug(self,s=10): print([self.get(i) for i in range(min(self.n,s))]) class string: def sa_is(s,upper): n=len(s) if n==0: return [] if n==1: return [0] if n==2: if (s[0]=1 and not(ls[v-1]): sa[buf[s[v-1]]]=v-1 buf[s[v-1]]+=1 buf=sum_l[:] for i in range(n-1,-1,-1): v=sa[i] if v>=1 and ls[v-1]: buf[s[v-1]+1]-=1 sa[buf[s[v-1]+1]]=v-1 lms_map=[-1]*(n+1) m=0 for i in range(1,n): if not(ls[i-1]) and ls[i]: lms_map[i]=m m+=1 lms=[] for i in range(1,n): if not(ls[i-1]) and ls[i]: lms.append(i) induce(lms) if m: sorted_lms=[] for v in sa: if lms_map[v]!=-1: sorted_lms.append(v) rec_s=[0]*m rec_upper=0 rec_s[lms_map[sorted_lms[0]]]=0 for i in range(1,m): l=sorted_lms[i-1] r=sorted_lms[i] end_l=lms[lms_map[l]+1] if (lms_map[l]+1=1 rnk=[0]*n for i in range(n): rnk[sa[i]]=i lcp=[0]*(n-1) h=0 for i in range(n): if h>0: h-=1 if rnk[i]==0: continue j=sa[rnk[i]-1] while(j+h1: mid=(ng+ok)//2 if ST.query(mid,p[L])>=d: ok=mid else: ng=mid query[ok].append((d,i)) cum=[0]*n for i in range(1,n): cum[i]=cum[i-1]+(n-SA[i-1]) ans=[0]*q seg1=segtree([0]*(n+1),lambda x,y:x+y,0) seg2=segtree([0]*(n+1),lambda x,y:x+y,0) stc=[] for i in range(n-1,-1,-1): if i!=n-1: res=0 while stc and stc[-1][0]>=LCP[i]: res+=stc[-1][1] x=stc.pop()[0] seg1.update(x,0) seg2.update(x,0) if res!=0 and LCP[i]!=0: seg1.update(LCP[i],LCP[i]*res) seg2.update(LCP[i],res) stc.append((LCP[i],res)) seg1.add(n-SA[i],n-SA[i]) seg2.add(n-SA[i],1) stc.append((n-SA[i],1)) for d,idx in query[i]: ans[idx]+=cum[i]+seg1.query(0,d)+seg2.query(d,n+1)*(d-1) print(*ans,sep='\n')