他要求的就是lcp(x,y)>=i的(x,y)的个数和a[x]*a[y]的最大值
做一下后缀和，就只要求lcp=i的了
既然lcp(x,y)=min(h[rank[x]+1],..,[h[rank[y]]])
那么我们求出来对于每一个h，以它作为最小值的区间的左右端点就可以了，这个可以用单调栈，具体做法见Neat Tree(?哪里具体了)
假设L是i左面第一个h小于等于它的，R是i右面第一个小于它的（一定要一边有=一边没有，很关键）
那就相当于lcp(x,y)=h[i] ,rank[x]∈[L,i-1],rank[y]∈[i,R-1]
数量就是这两个区间大小乘一下，最大值是max(最大值之积，最小值之积）（因为会有负的），这个可以用ST表来做
貌似并查集也能做 但我哪会啊
写的这么辣鸡 开着O2才勉强水过洛谷 哪敢到bzoj去交啊
upd:
(Time Limit: 10 Sec)
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=3e5+;
const ll inf=1e18; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int N,M,deli[maxn],sa[maxn<<],rnk[maxn<<],rnk1[maxn<<],tmp[maxn<<],h[maxn<<],cnt[maxn];
ll ans2[maxn],ma[maxn][],mn[maxn][],dt[maxn];
int stk[maxn],sh,rg[maxn];
char s[maxn]; inline void setsa(){
int i,j=,k;
for(i=;i<=N;i++) cnt[s[i]]=;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) rnk[i]=cnt[s[i]];
for(k=;j!=N;k<<=){
// printf("%d %d %d\n",M,k,j);
CLR(cnt,);
for(i=;i<=N;i++) cnt[rnk[i+k]]++;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) tmp[cnt[rnk[i+k]]--]=i;
CLR(cnt,);
for(i=;i<=N;i++) cnt[rnk[i]]++;
for(i=;i<=M;i++) cnt[i]+=cnt[i-];
for(i=N;i;i--) sa[cnt[rnk[tmp[i]]]--]=tmp[i];
memcpy(rnk1,rnk,sizeof(rnk));
i=;rnk[sa[]]=j=;
for(;i<=N;i++){
if(rnk1[sa[i]]!=rnk1[sa[i-]]||rnk1[sa[i]+k]!=rnk1[sa[i-]+k]) j++;
rnk[sa[i]]=j;
}M=j;
}
for(i=;i<=N;i++)
sa[rnk[i]]=i;
}
inline void seth(){
for(int i=,j=;i<=N;i++){
if(rnk[i]==) continue;
if(j) j--;
int x=sa[rnk[i]-];
while(i+j<=N&&x+j<=N&&s[i+j]==s[x+j]) j++;
h[rnk[i]]=j;
}
} inline void setma(){
for(int i=N;i;i--){
ma[i][]=mn[i][]=deli[sa[i]];
for(int j=;i+(<<j)-<=N;j++){
int k=i+(<<(j-));
ma[i][j]=max(ma[i][j-],ma[k][j-]);
mn[i][j]=min(mn[i][j-],mn[k][j-]);
}
}
} inline pa getma(int l,int r){
int k=log2(r-l+);
return make_pair(max(ma[l][k],ma[r-(<<k)+][k]),min(mn[l][k],mn[r-(<<k)+][k]));
} void solve(){
for(int i=;i<=N;i++){
while(sh&&h[stk[sh]]>h[i])
rg[stk[sh--]]=i;
stk[++sh]=i;
}while(sh) rg[stk[sh--]]=N+;
for(int i=N;i;i--){
while(sh&&h[stk[sh]]>=h[i]){
int r=rg[stk[sh]]-;
pa x=getma(i,stk[sh]-),y=getma(stk[sh],r);
ans2[h[stk[sh]]]=max(ans2[h[stk[sh]]],max(x.first*y.first,x.second*y.second));
dt[h[stk[sh]]]+=1ll*(stk[sh]-i)*(r-stk[sh]+);
sh--;
}
stk[++sh]=i;
}
} int main(){
// freopen("testdata.in","r",stdin);
// freopen("aa.out","w",stdout);
int i,j,k;
N=rd();
scanf("%s",s+);
for(i=;i<=N;i++)
deli[i]=rd();
M=;setsa();
seth();
setma();
CLR(ans2,-);
solve();
for(i=N-;i>=;i--) dt[i]+=dt[i+],ans2[i]=max(ans2[i],ans2[i+]);
for(i=;i<N;i++)
printf("%lld %lld\n",dt[i],dt[i]?ans2[i]:);
return ;
}