目前90分，wa在luogu #6 #19 目前不知道是哪里的问题，有可能是SA写挂了

#include<bits/stdc++.h>
#define int long long
using namespace std; 
const int N=1e6+10;
int sa[N],x[N],y[N],c[N],rk[N],ht[N];
int a[N],Max[N],Max_[N],Min[N],Min_[N],siz[N],fa[N];
int find(int x)
{
	if(fa[x]==x) return fa[x];
	return fa[x]=find(fa[x]);
}
vector<int> lcp[N];
int ans1[N],ans2[N];
int f(int x)
{
	return x*(x-1)/2;
}
signed main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout); 
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int n,m=128;
	cin>>n;
	string s;
	cin>>s;
	s=' '+s;
	for(int i=1;i<=n;i++) c[x[i]=s[i]]++;
	for(int i=1;i<=m;i++) c[i]+=c[i-1];
	for(int i=1;i<=n;i++) sa[c[x[i]]--]=i;
	for(int i=1;(1<<i)<=n;i++)
	{
		int now=0;
		for(int j=n-(1<<i-1)+1;j<=n;j++) y[++now]=j;
		for(int j=1;j<=n;j++) if(sa[j]>(1<<i-1)) y[++now]=sa[j]-(1<<i-1);
		for(int j=1;j<=m;j++) c[j]=0;
		for(int j=1;j<=n;j++) c[x[j]]++;
		for(int j=1;j<=m;j++) c[j]+=c[j-1];
		for(int j=n;j;j--) sa[c[x[y[j]]]--]=y[j],y[j]=x[j];
		now=0;
		for(int j=1;j<=n;j++)
			if(y[sa[j]]==y[sa[j-1]]&&y[sa[j]+(1<<i-1)]==y[sa[j-1]+(1<<i-1)]) x[sa[j]]=now;
			else x[sa[j]]=++now;
		m=now; 
		if(n==m) break; 
	}
	for(int i=1;i<=n;i++) rk[sa[i]]=i;
	int p=0;
	for(int i=1;i<=n;i++)
	{
		p=max(0ll,p-1);
		while(sa[rk[i]]+p<=n&&sa[rk[i]-1]+p<=n&&s[sa[rk[i]]+p]==s[sa[rk[i]-1]+p]) p++;
		ht[rk[i]]=p;
		if(rk[i]>1) lcp[p].push_back(rk[i]);
	}
	for(int i=1;i<=n;i++) cin>>a[i]; 
	for(int i=1;i<=n;i++) fa[i]=i,Min[i]=Max[i]=a[i],Max_[i]=-1e18,Min_[i]=1e18,siz[i]=1;
	memset(ans2,0xc0,sizeof(ans2));
	for(int i=n-1;i>=0;i--)
	{
		ans1[i]=ans1[i+1],ans2[i]=ans2[i+1];
		for(int j:lcp[i])
		{
			int x=find(sa[j]),y=find(sa[j-1]);
			fa[x]=y;
			ans1[i]-=f(siz[x])+f(siz[y]);
			siz[y]+=siz[x];
			if(Max[x]>Max[y]) Max_[y]=max(Max_[x],Max[y]),Max[y]=Max[x];
			else Max_[y]=max(Max[x],Max_[y]);
			if(Min[x]<Min[y]) Min_[y]=min(Min_[x],Min[y]),Min[y]=Min[x];
			else Min_[y]=min(Min[x],Min_[y]);
			ans1[i]+=f(siz[y]);
			ans2[i]=max(ans2[i],Max[y]*Max_[y]);
			ans2[i]=max(ans2[i],Min[y]*Min_[y]);
		}
	}
	for(int i=0;i<n;i++) 
		if(ans1[i])
			cout<<ans1[i]<<' '<<ans2[i]<<endl;
		else
			cout<<0<<' '<<0<<endl;
	return 0;	
}