写了一个一看就是错的的东西直接过了。这个会算重很多东西。

#include<bits/stdc++.h>
using namespace std;
char s[20000005],t[20000005];
char st[20000005];
char rev_st[20000005];
int z[20000005],rev_z[20000005];
int nxt[20000005],ans[20000005];
void Z(char *s,int *z,int n){
	int l=0,r=0;
	z[0]=0;
	for(int i=1;i<n;i++){
		if(z[i-l]<r-i+1) z[i]=z[i-l];
		else{
			z[i]=max(r-i+1,0);
			while(i+z[i]<n&&s[z[i]]==s[i+z[i]]) z[i]++;
			l=i,r=i+z[i]-1;
		}
	}
}
void KMP(char *s,char *t,int *nxt,int *ans,int n,int m){
	for(int i=2;i<=m;i++){
		int p=nxt[i-1];
		while(p&&t[p+1]!=t[i]) p=nxt[p];
		if(t[p+1]==t[i]) p++;
		nxt[i]=p;
	}
	for(int i=1;i<=n;i++){
		int p=ans[i-1];
		while(p&&t[p+1]!=s[i]) p=nxt[p];
		if(t[p+1]==s[i]) p++;
		ans[i]=p;
	}
}
void KMP1(char *s,int *nxt,int n){
	nxt[0]=-1;
	for(int i=1;i<n;i++){
		int p=nxt[i-1];
		while(p!=-1&&s[p+1]!=s[i]) p=nxt[p];
		if(s[p+1]==s[i]) p++;
		nxt[i]=p;
	}
}
int r[20000005],l[20000005];
bool vis[20000005];
int c[20000005];
int cnt[2][30];
vector<int>peri;
int main(){
	scanf("%s",s+1);
	scanf("%s",t+1);
	int n=strlen(s+1),m=strlen(t+1);
	for(int i=0;i<m;i++) st[i]=t[i+1];
	st[m]='$';
	for(int i=0;i<n;i++) st[m+1+i]=s[i+1];
	memcpy(rev_st,st,sizeof st);
	reverse(rev_st,rev_st+m);
	reverse(rev_st+m+1,rev_st+n+m+1);
	Z(st,z,n+m+1);
	Z(rev_st,rev_z,n+m+1);
	KMP(s,t,nxt,ans,n,m);
	int limi=n+1,limj=0;
	for(int i=1;i<=n;i++){
		if(ans[i]==m){
			limi=min(limi,i-1);
			limj=max(limj,i-m+2);
		}
	}
	for(int i=1;i<=n;i++){
		if(i<limj) cnt[0][s[i]-'a']++,cnt[1][s[i]-'a']++;
		else cnt[0][s[i]-'a']++;
	}
	long long ans=0;
	s[n+1]='z'+1;
	for(int i=0;i<=n;i++){
		if(i<=limi) ans+=max(limj-1-cnt[1][s[i+1]-'a'],0);
		else ans+=max(n+1-cnt[0][s[i+1]-'a'],0);
	}
	int len=nxt[m];
	while(len){
		peri.push_back(m-len);
		len=nxt[len];
	}
	for(int i=1;i<=n;i++) r[i]=z[i+m];
	KMP1(rev_st,nxt,n+m+1);
	for(int i=limj;i<=n+1;i++) c[nxt[m+n-i+1]]++;
	for(int i=m;i>=0;i--) if(nxt[i]!=-1) c[nxt[i]]+=c[i];
	for(int i=m;i>=1;i--) c[i]=c[i-1];
	for(int p=1;p<=n;p++){
		int i=p+r[p]-1;
		if(vis[p]||i>limi||r[p]==0) continue;
		ans+=c[m-r[p]];
		for(int j=0;j<peri.size();j++){
			if(peri[j]>=r[p]) break;
			vis[p+peri[j]]=1;
		}
	}
	cout<<ans<<endl;
	return 0;
}

一个 hack 数据：

输入：

bcaacbbbaaaacbcbaaccacaaaacbaabbacacbacbabaccbacababbcabacacaaccbabbbcaccaaccbaaccccbcbaacaacbacbbbcaccaabacbaabbacbbcbaccabccabbaabcacbaaacbaabaaaabbcbaacbacbacacbabacaacbaaccccbccbbababaabcbacabccbbccbcaccabcabcaabccccbccbabacabababaaabccaacbaacbbaaaaccbbababbbabccbabccbbccbaaaaacbabaaccaaccababcbaaabaacbbbbabbaabbacabccbcacbcaaaacbbacbbaccaaacbaabbaaacacabacaabcbcaaababcaaaabcccaabccabbcbbcccaabcbccaaaacabbbacababaabbabccacaacbcbbcabccbcbbcabaccbaccacabaaaabaaabaacbacbabacbbbbaaaccabcacaabcbacabcaaacbcbbcabbcaaacaaacacccbacccccbabbcaabaaaacaacabaabbcabcacbcbccaccacacbbaabcaabcccbccbcabacbabcaabaacacbcabcccbcaccbbcaaabacbbacbbcbbcaccaabbcccbabaabaaccccbbbccbbcacbaccbbaccabaaaaabaaacbcaccbaaccbcccaababaaaabaaaaacabacccbbaabccaaabaccaaabbbccbababcccbcabbbaacaacabcccccbcacbbacbbcbbabacccabbbcabbbcbccabbaacacbbccabcaacacabccccabccaacbbcbcccbbabcbcccccabcbccbbbaacbabbcccaaabbcabbbbccccaaabaaabccccccacbbacaccaccccaaabbbbbcccababacaabbabaaacbababacabccbbaaccbacbbbcbaaccbbcbabbcbcabccbbbbccbacbbbbabcbacbaababcccbcbbbcacbabccbabaaaaccbccbaccbbcccaaabcabcbbcbccccbccaabcbccbbcabcabacbbccbccbbccacbababaacabacbacbcacacbcaacbbcacbcccccccbbbbacbabccbbccbbbacbbbbacccaccabbbabcaccbcccccbabbccccccbaabbaaaacbccccbbcaabbbaccccbaaabaccbacccbaaabccaccbcacbcaaaaacbccccbabccaaabacbcbabcaacbbcacccacccbaacbaaabbccacabacbccccabbacbabbcacaabcbcabcbcbbcaaaaabccaabaaaaaababcbaaacbcbbcbabababbcbcbcbabcacbcbbccccababbbcbcccaaabacbcaccbcbaacabcbabcabbccaaaaabbbccacbcbccacbcbccbbbabaabbcbbbbabbcbbccacbbaaacbccbabbaabaababbcaabacbcabbbacbbaababcabccaccacbabaaaacaaabbbbbabbabcbbbaaacabcabcacbaaaaaacabbabaacccacbbaacabcbbbcaccaabbcccaababbcccbcacaacabacccbccaccbaacbcbaaaabbbabaabcbbcccacacabcbcacabbcbcaaccbcaacacbbbaabbbababbbabbcbcababcbabaaaaccacacaccbbaaabccbabbaaccbbcabcaccaccccbbbacbcbcbaccaacaccaccaabbcbbbcbbbbcccaaacccabaabbaacbabbcaabbccacbabcaaaabccaabbacaaccacabcacaaaacacaaaacbcabaacbbaabbaaacccaccbcccaabcaccbccaaccabcabacabcabbccaaaabccbcbcacccaababacbcbaabababccbaabccbcaaacbbabaccbbaacbacacbbcbbcbabcbcabccabbcbbbaacaabbcaabacaccbbaaaccaacbaccaaabcacccccabaaaaababbbcbacccabcbcbbcccbcbbaccccacaccccbcccbcbbacbccaacababbccbabacaaaccaccacabbabcbabcbcaacabbaaccccacbbaaccacaaacacbbbaacaabaccababbbacbaaacacaaccaacacbbccbabcbabbacbccaccccbcabaacbccabccccabbbccccacaaacbaccabaaaaacbbcbcaacbabacacccabaacaabbbacabbccaaacabccacaabcbbbbaacacccbcabbbaaacccccaccbbbabccabaacaacabcccaaaccccbbcbacabcbcaabcbbbcccabbabbbacbcacabbacbcaaacaaccacbcccabcbbccbabaccabbacbbbcabbaaacaccbababcabbccacacbcbaaabccaacaaacbbacabbccaaabbabacabcabcccabcacccabacababccacbaaabcbababcbcccccbcccbccbbacaaaaabccabcbabbbacbaaacacbabcccaaabaaaaccacccbcacaababbcaaacbbbaacbcbacccababccbcbcbbbbbcabcbbaccbaaabbccabcabcccabcbbcbbabcccbababacbcbcaacbacbcbcababbabbaabbbabbccbacabaabaaccbbccabaaaabbbaaacbccaabacbcbabbacaaacacbbcacabcccabbcaccbbacccacccbaaaccbbcbbabbbaacbabacacaabbacacaacaccbbabcbabcbbcccbaaaaabcbaacbbbbaaccaacaabacaabcabcacaacbaaaaaabbcbbacbaaabbccccbabcabbaaabbacabcbabbbbabccaccbaccabbbbbacbabbcbacbcccacacaccaaacbbbacbacaacccababcabcccaaaccbabaacabcaccbcbcbbbcccccacbbccbcbacaabbbcaabcbcabaccbaaacbcabccbbbabbabcbabcabacacbcbaaacabbaaaaababaabcbcaacccbbbacbbcbbccabcbaabbbaabbbbbabacbccbcbbcbbacaccbbacaabbaacbcbbbcabccabaabbcbaabbbbaaccabbababcbbacabacccaabbcbcbabcabcccbacaaaaaacababaccbcaacaacaabaccaaabacccccbacbbbcbcbbcaaacabccacaccabbaccbacccacacaabbbccaabbacccacaacbacbbccaabcbbabbccbccabcabbccbcaabbbaccbacbbaacccbccbcbaaacbabcbaaabccbcabbbabbabccaacbbababccccabbbacacbbcbbacbbbccbabaaaccbcccccbabbcabcccbcbbbabccbcbaacaaaacabaabccbbccbcaaacaabbaccaaccccabaaccbbcababbcbcabcaaabbbcacbabaacabababcaaaaccccabcabaccbbcbacaabbcbbccccbcbccaacacbcbaaaabcbccbccbcbbbcccaaccbabababacbabbcbcacbbccbccabcbacbcacccccbacbbcaabcaacbbcabbababaacbbbacbbbcacccaacbbccacccaaccbcbbaccccbcbcabaacbcabbbbccabcbacbbaccacccabaabccbabcaccacaabcccabbccbbabcbcabcbccabcbabcbbabbaacbbbccaabaaacbacbcaaccbabcbccaaacbbcbabcbbccbcacbaacbbcbabbabbbacaccabccbbcacccbbbbcaaaacbabaaaaaaccccbcaabbccaacaababbaacaaaaaaaabaaccbaabbcabbcbbcbababacabccbabacbbbabbbbabaaacbbbaabababacbcababcabbcbcaaaabcbaaccbababcbaacccbcacaccbbbccaacacaacbaccbaccbcacbbbcbbccbbcabbbccabccbcbabacababaaccccaaccbcbbacaabacaababbaabcacababccccbaccbabccbcccbaababbccbbcaabbbbacaabbbcbaccabbccbacbacabbbacaaacaacbcbbacaaaacacacacbbaabbcaaaabcbacbaabaacbbcbbababaccbcbbcaabbbccbcbccabaccacacaabbcbccccbaacbcabbbbbbbbacabcbaaaabbacbcacbcccacbbccbaaacabbcbacbbaaacaabcbbaccababcabaababaabaaaaaabaaabccacbaabbaccccbbaaacbcabbbbababacbcbccabcccabccaacbbaaccbaccbaabbbabcbcacbcccbbbcaaacbaaaccacbababcabacacbcbbcbacaacbcaababcbbaaaacccabccaaaccabbcacacacbaaaabbabaacabcabcbaacbcbabacbccbbabbaccbbacaccccbbacaaabbcbbaacbbbabaccacbaaaacabbcaccaccbccaccabbbacaaababbaaabaacbbabccccbcbaaccacacacaabccaabcbcbbcbabbacbbbbcbbbacaabacbcbbcbbbabaaacccccabcbbacbabaacbccbbaccbbbbbbcaccabcbcacccbccabbbbaccbacbacbaaacbcabaccacbbaacbabcbabacccabcaabaacacaaaaaaaabcaabcaababbcaccabcbcaabbbcbacaccbcabaccbacbaababaaabcaaabccbabaccababaaaccaccbccbccbaccbcaccbaababacbbccababcabacaabbbbbbcabbbbbacacaccbcbbaabcbbaccbbbbcccccbaacbcaabbccabbcbbabcbabbababbbcabacabaccacbccccbacbaaccbbabbcabcccababbccbacaaaccaccbaacaacbbccaacabcccccbbacabbbccaababcaaacaaabbacbaabbabbbcacbbaccbcccbacccbcbacbaabbacabbaacbbbbbcbabcabbbaccabbbcaabccbbacbaccccabccaaacbcbaaccbacaabbccbcabbaacbcbaaaaccbbbaccaaccccbcaacaccaaabcabccccbccabbccccbccbbbcbacbbbbaaacaaaaaaaaacacaaaaacccacbcaaccaaaccaccacaabacabcbbccacbcaaabbbacabbacabbbbabcabbbbaaababcccacabbacbaaaacbcabbcabcbbbbbbaabbacaaaacbaacbcccbabccbcaccaacabcabacbcabacccbbccbaabbccbaacbbbaabccbbbaacbbabccaccbbbcbaaabcacaccbccacccbaabacabbaaccaacbbbaaacbbbccbbccbacaccbcacbaabccacaaccbacbaccabaaacbaabbcaaacbbabbbbabcabbacbacbbaabbaaccabacbbbbbcccbbbacbbcaccbaabbcabaabcacbaccbcbaacabbbcccbabbbabaabacacacacbcaababbbaabcbbbacbccbccabaacbbcbcabbcccabcbbabaabbcaccbbacbaabacbaccabbcccbcaccbabcacbccaccbcbbacbcaccbabaaccbacabaccccacbaabacabbaaaaaabaaabacbbccbbbbbcbcbbbaccabcccbaababccababcbcbacaabbabcbaacbcabacbaccababbcbcabcabbbaaaabbaabcaaccbaabccaacbbcbcbbaacaabacacbcaacabbccbcccababacacbaaacbcbabcbbcaabacacbabaaabaaabcbacabacbccbcbacccbbabbbaacaabbbcbbabcabacbbcbabbabcbbbbbcccccbacabcbabaaccbcccccbbacaacbacbacccccbcccbcacbcabbbbbcaabbbbbabcccbccaaaacaaccababcbccbbccbcaabbacabcbaabbcbbbaaabbcbcbaababbbbaaacbbbaaacabbbbbbcbbcbbcaccbbaabccacbaccaccacaabaccaaaccbbcaaabcbbcccbbabaaaabacccaaaaacacbabaccbccaccabcbbcbabbaaabbcaccaabcccbacbcaaaacbaaabbbcccacabbbcbcbcabcabcaabcbabcaabbaaacaaaccccccbcabcababcaccbbaaabbbcbcbabaaccabccccaabbccabacacabbcaaacbbcbcbcbccbccabbaababbabcccaaccbabbccbbccbabbacbcbcccbbbabccabcbcbcaababacaaacbabcbbabbbabbbabbccabccccaacbcbcbccbaaccaaccaabacacaaaaabaaabacbbccabcbaacacbbcaacababaaacbcccbabbccccbcccabacccabcccacaacabbabccbbccbcabcaccbcbabbacbbacbacabbbccbbcacbbcabaacbacaaaabccbbcbaaccccbbbbaacbcbbccabbcbaccccaabcacbaaaacbcbacbabbbaacababaaabcbbabaabcbbaabaacbcabcabbbacbbabbcbbccabcccaacbbbcacaaabbbcccaaaaabbcbccbcaabaaaccabaacccacbbbbcbcbbbbcaaccaacbbabcaacbbccbacaaacaabbccacbabbaaababbccccabbbbcacaaababacaabacacbbbacccacbbcaaacacbbaaacabaabcbbcbcbccacbbcccacccbbaaabcaacacbbcacbabbbbcbcbbcabacbcacccabcbcccabacacbaacbcacbabbaccbabcbbaaaaacacabbcbaccacacbbbbbacbbccaabbababbbbacbaccabacbabbbbcbbcaaabbbabbbbbabbcccbbbbaabbabacccbaccbcccbcacacabccacaabcabbccccacccbbaaabbaaabbbacccaabcbbcaabcbcccacacacbacbccbabacacbccbbbaaaacccaccbbbaccaabccbbabbcababbbacaabacaccacbaaccbacbbcabbbcaaabbaabaaccaaabbaaababbbabccabbbacccbacbacccacbccaacbaababaacbaacbccbbacccabbabcaabaacccbcbaccaacabacaabbabacbbcabbbaaacccbaacbcbaabcbacbccaccbcaabbabcaacaabbbabbaaaccabcabaccabbcabaacbaacacacbaccacaccccaaaacaabacbcbbcaabacccccbbacccbcbcabcabcbabbbcaacbcabcbbcabbbbbcbbbbcaacbaaabaabbacbaaaaaaacacaabbcbccabababbabbabacbbccacbccbbabcaccabaacbbbcccbcbbacbaccaaaccaaaabbbacccbcaabaccaacacaccbabbccabacacbbcbabbbccbcaaccacbccaabaaccbabcacababbacccaabcacaaacabaacbccbcacabaacbacbaccaccccaabaacabcaabbcaabbbcbccbcbabcabbacbcabbcabbcaacccccbabacaabbcbababccacacbccbcbbabbccaccaaaacacaaaabcbcababbccbbcbcacbabaacacaaccbaccabbbbcbbcabcbbaabababcccbcabbbbacacbbcbccbcbbaccbcabbbbbccbaaaabcbccacabaaacabacbcccaaccbbcbaacabacbbbbcabcaabbcaaacaabacabaababbbbacbaaaabacaacbbbbbbbabbcabbaccbbccabbbbacbacacabbaccabbcaaabcbacbcccbacbacacccaacabccacbbbcabbaccccbbbabacbbccaaaaccbabbabaacaaabacaabcbaabcaaaaaaaacabcbbbbbcbaaacccccaacaacabaaabacbccbacbcaabcabbaabcaaccccababaacaaaacbcbbcbbcccaaacbbbbbcababcbaccbabbbcbaaaacaabccbcacbabcbcbacbbacaababccbbacccacaabacacbaaaccacaaaccbbbbaccbbabcaccacacabcbbaabbcaabcbbbaccbbabcbbacabcbbabaccabcbaaccbababbacacacabbcaaabcaabccbabcbbcacccccbacbacacbbbccbcbbbcbacccacbaccacccccbcacbacbcccaccacbcbcaccbbabccbbaabaccccacbcaaaabbcbccacbbcaabccbaaaaaccccccbacbabbacbabcaabacabbbccbcbbacacbaabbccccccbccacacaacabbcacccabbacabcacaccaccacbbccbaababaaacaabcbbbccbcaaacbaaacccbbbbbaaccccabccbaabbacbabbcbcbbcbccccacccbaaccccaabcabbbcabccabbbbacbbbabaabaaacaaaaabaaaccbcaabaaabacabbabbacaababcbaabcaacccaabcabbbbccbacbccbcbaaaabccccabacacaabcacbbcbbcaaaacbbbbbaaacaabcaacbaacbcbbaccabaccccaccbaccbbccaabcbbbbcaabcbbbbabacaacaacbbabcaabbcbabbcbabbbaabbaacccaabbcaccacacacbccabbcbbcbaccccbacbcaaaabbbbbcbaacaababcaabccaabbcccbbcccbacbbbcbabacbbcaacabbabccbccbbaabcacbabcbcabbcaacaacacaacbbaccbabcbbcacabcccacabcbcaacbabcabbcccbcccaabcbcbbababccbbbcccbcbccacbacabacacaaabcabcbacaccbbacccaaacbaaaccaacaabaabaaccbacaccbaabaacbaccbbbacaabcbccacbabaacaaacbbaaabbcbccbbbbbcacccaaacbacaabcbaaccbbcaacbabbabacbbabbbbbcbcccccbcccccabbcabcbacacccbaacaacbaaccbcaaaacbbacaccccccbcabacabbabcaaacbccabcbcbcbcbbabbabbaaaaaacaacbcbabaacaaaccaccabbbbbcabaaacbbcbcaabbbacbaaacbcacbccaccbbaaabcabccabccccbcccbacbacccbaaaccbcccaaccbcbbaaacbccaacbcbcbbcabcbcccbcccaacacbaacbbaabbbbcaabbcbcaaabaccabbbbccbbbcaaaaababcccacaacbbbbcaaaacaaccacbcaccccabcacabcaacaacaacaacabaaaabbbacbabababbbaabbacaacccbaabacaacaaacacaccaabcabccbcaabbcabbcacbbccbcbbaccaabbcaabcccbaabaabaccabccccaaaaaccabccbcbcabcbcbbbbcaabcacbbcaabababbabaabccbbcabaacccacacaabcbbaaacbbbbaaacbcbcbaacaccbaaccbbbcbaacbabaccbbaaaaacccabcccbabacbabccbccccababbbbacbbcccaabccbccaaabaacaacaaabbbbbbcbbcbaaaacbccbaabcbccacbababcacbabbabbcbccabacaaacbccabbbbbbbaabbabcaabbccbcbaacaaccbcbcacaabbbacbacabcaaabaaccaacbcaaacbabaacabbbbcbaaaabbaacccbacbbaacababbabccbaaccbccccabacbbaabbbbbbbbbcacbcaaacbbabbaacccbbbbcbbbabbaabacabaaaaccacccaaacbbcaacbcababacaaaabcbcccababccbcbbbcbacbcabbcacaccaaacbbabcbbbcccaccbbabacabbbbacbbbbcaabbbbabcccabaabcaabbbbbbaabaabaabcacbbcacabaccabbbaaabcbabccbbacacccabccacbbcbbcbccbaccaacbaaacbabbabcaccbbbbaacbbbabaacbbbabbabccbccbbbbbcbcacbccaabacbcbcaccaaccababbcbbaabcbbcabbbabacaabbabcacbccbccacbbccaccbababacabcbcabcbbabbbccabcacbcacacacbababbcacaaabbbbcacacabaabccacabaaacbacabccabcccbaaabcbcbcccaabaaaaaacaacacbcbacbccabaacabbbccabcabacbcbbabcbbbccccacbcaaccbacbaaabcbccbbbabcabcaaaabbbacaaccacacacccacaacaaabbcabbacbbbacacaabaccbbccbccbcbaababbaabccababcbcbccbacabbcacbcacccbaacaaabcbbbabbababbbccbbbbbcabcabaccaabbbcbcbaaacaccbbababcbbaacabaabbbbacccbabcccbbcccacacaabbcbbabcccacabccbbcaabcccbbcabbccacaaaacbaaabacacbcbbccbbcacccccaacaaabbacabbaabbcbcabacaaabababcabccacbabaabbabcccccbcccababbbbcbbcbaaabcaacbbabcbcbabccabcbabcabacbccabbcbbbbcabcabccacbaaccbccaccaaaacccacbacbcbcacabbaabaaccbcacbacaabcbcacabbaaacabcbaacaaabcbbbbbabaacaaccacaacbcbcacabcacaaccaabcbacaabababaaccccbbbbaacbaacbcacccbbbaacbcbcbcaabcbbcabacbccacacabbabccbbcbbaaccbbaccbccbacabbbacbbacbcbcccababcbbcccbaabcacacabacbabbcaaabacaaabbbcccccabbbaaacaaacacccabcbcbcbccccbbacacaaaaacababcbcaccbabcccabcabcabbbbacacbacbbbaabaccbbaacbababaabaacabbbaccccacaabcaacbabcabccbaccbcbcacaaabcbbabcbaababccccabbacbccbacbacbbcaabbcbcaabccaabccaccacabaaabaabccacacbcbbaacbbacabacbbabbccccacaabbbcccabbabbbbbacabcacaacaccaacabcabcabbccccbccaaacbcabbababbbcbbacaacbcbaaabccaacbabaccbbacbbccabcbbaabacbcaccabacbbabbbacccbbbaaaaacaacccbaabcaaaccaaaaabaabbbccabbbcbbaaaabbcccbbcbbacacacaabcabaccbcbbcacbabaacabcccbaabbcbacbabababbccbaabcbaababbaabaacaabcbcbacabcabcccaacaccccabbcbcbabcabbbbaccaccabbccbaccaaccbccbbcacbaacabcccbccaaccaaccaaabbaccaccacccbccbababacabbbabacacccabaaabaabbacabaabbcabacbbcbaccabbbabaaabbabbaaababacaabccacbcacbbabbcaccbbaabbccccbacbabcabbbbccbccbacaaccccacaaacccbbbbbaaccbabaabbbbacaabbbcabccaccacbacabccccabcbaaccccabcaaaccabcacccaaccaacbcbbbacaacccabbcbbaccbbbaababccabcaaccbccbccbacbabbaccbbabaccbccbaababcabcbbbcabcacacbacccbbbbaaacacbbbbbbccccaccabbcaacabbcaababcacccbccabaabaacbbacccbccaabcaccaccaaabcccbababccaaabbbbcacccbcbccbbbaabbabbbabbaacacbbcaacbbcbccabacccccbcbbbaabacbacccaccbcbbbabbaacbacbaacbbbccbcaabbbbcabcaaaacbabcaccbabcaaaaabaccbccacabcabcaabcccbbbccaabbbbbacbabcababaacccabababbbabcaabccbaacacaacbacbbcccacccbbcbbcbbabcbcbcacccbbcbbabbbccabaacabbccacbbaaabaacccbaaaacbccaaccabcaaaccbacaaabbccbbcbaaaacccbbbcbbbbabbaaabcbaacbcaabcabccaaaccacabcbbacbbcbbbcbccbabcaabacbacaacabababaabacbcaaaaccabbbbcabbbabcbaccacbbcaaccbcccccbabcccbbcbabcbaccbacababbbacbaaabbbabccbaabbaaacbccbbcbbabcbbcacabaccccbbbaaaacbacbbaacbaaabbaacaccccbcbaacabcacacbccbacaabcbabacabaccbaaacabacabcaccbcaabcccbaacababcaabbacbccccbabcaccbcabbbbcbaacbcabaacabcbabaaacabccccacbacbbbbcaccabaccbbcccaacabbcbcccaabcbbbbaabbabcbbacbaccbcbacabaaaccbaababbaacccbbbcbcbabcabbcabcbabbcaccbccbbcaccacbbccccaacbbcccbbcaaabaabacacccaabaabacaccbabbccbacbababcbbabbcbacbcacaccaacccaaacababcacbbbbabbaaaabcaacbbbabcbcabbabbaabaaabbbbcaabcbacbcbabcbbcacbcaaacbbcabababaccbbccbbabacbbcaaabbabcbabccaabcabbacacaabaacaaacbbaabcacbabcacbaccccbbacbbbbbbbcbbbcbbbaacccabbbaabbaabaccbbbacbabcabcccacabccbabbbabaabcccbabcabaabbbccbbbbbbcbcbaabaaaaccacaabaabbcbcacccacabaacacaaaacbacaacabaccaaacaccacaabababaaacbacacacbcbbccccabaccbacbcbacacaaacababcbcbaaaabcbaabbabccacbabbcabaacbcbbacaacbbcccccbbacbbcabbababbccaaaaababbabacbacccabcbbaacccacbbcbabbccccacbbaacccbaacabcbbcabbbcabaaabbacabcbcaabaccbaabbbcacaccacbbcbaababbcacacabbbcbaabccccabccbaaaabbbabaaccabbbcabaabaacccabbaacacbacbacbbcbaaaacacbbccbacbccccaccabbbbbbbccccaabbabbbbbccacaccbacbbbabaaacabbaccaaacccbcbccbbccabbacabccccabacccbaabbbcccbabcbacbbcbccabccbbbcaacaababbcccabaacacbcbcabcacccabbacbabbcabcacaccbcbccacaacbbacaaccbacbcaabbbcaabbabacbaabccbcbaacacbcbabcccaaacbcbbbababcabbbbaccbbbbcbccbabcccabcccbbbccccbbaaabcababaaabccaacbaababbbccabaabbbbacbcbabacbcbcbcbacababbabacbbacacaabcaabbcaabbcbaababbcbaabcabbbcbbccbabacabbbbbcbcccaabaaacaacacabbbbcabbbcbcbbcbacaabcababbabcbcbbaaaabbaabccbaaaabaabcabcaabbbbbbbcccbcccaacccccaacabccccccbcacccacabbcbbaacbacbacbbcccccaabbacbcbccabaccbcaaababcbbaacccabacbcccababbbbbaaacbcabccababbcbacccbcaabcccacababbbaacbbaabcbacccbcaccbbbacbcbcbaaacbacacbbcaaaabccabacaccabacbcbccbbcabbcacacbbcbaabacacbbcbbccbbccbcacabcabbabbabcbcabbccbcacbcacbbbbcccbbacbcabcbbbbacbaccbbcbacccbabcacbcccaccbccaacabacbacbacbacbabacccabacbaaccccbaabbcaccbbacacaaabcabbccaaabbcbcbacbcbbacccbbcbababcabccabaacacbcbcacaabaaaabaabccaacbaabaccbaaabcbcbcaacbbccbbcbbcaacacaaaacaaabababcabbbcacbcbbbcbccabcaabbbbbacacbacbccccababcbcbabaaaabcacabbccababbcaccbbbbccacbcccabbbbabcacaabbbcbbcaaaacbbcccbcbacbacccabcabacbbabaaaabbcbbcbaaabbbccaabccaccacbacaaccbcccbcbaaacacccbbaccbbacbbacabccabcaaaccbccaccabbbbacccbbbacabcccbbabacabcacccaccacbbacaacbbcabcbbaababbbaacaaaacbabcccbbbbacaaabccabcacbbaabccbaabbacabccacababacccabbaaaababacbabaacbaccccbbbabcaaacccccacacbaabaabaacbcababbccacaacaabcaaccacbabaabaccccbbcccabcccabababbaaaaabbbcabaacbcacbbcbbaacccbccbbcbbabbaababcabacbbbbacbcccaccacbccaacaacaababcbaaacacccbabaacccbaaaccccbbccbccbabbbacacaabcacaabaacbacabaabaabcabbbcbbabbabbbbbaccabccaacaaaaaccbabccbcabbbcbcaabcbaaaababbbbaaabbabaababaaccaccbbbaaaccbbcabaabcacbbbacbcaaccccbcbccaacabbaccababababaaaaccacaccbaababcccbaaccbaabaacabbccbbcaacabaccbbbcaccbcbbbcacccbccabbbabbccacabcaababcccababcccaaabcbaababcccacbcaccbcbbcbcbacaaaabcbcbbcabbbaccacbcbcababbacbacbcbbaccbbaaaaaaaacccbcbcccbcaabbacbaacacabcabababccaaacbcccccbabcbcbcbcccbcaacaaccaacbcaaaccbaabbcbaacccaacbbabbcabccbcabbabbccccaaabcbbaacbabcabacbaccbccacaacaaabbbaccbaccacbaacbacbabcabaaccccccccaaaaccbacaaabacaccbbbacacbaacbccbcaaabbabcbbcaacaabacaaccabcbcaacbaabaccabbabbacbbbaaccbacbbacccacbcbbcabcbabacccbccbcbabbbbccbacbccaaaacaacacabbcabbbaccabbccaabbcccaccbababbbbaaacbacbbcccaaaccacabaaccbaaacaaacaabacbcabccccabbbbbbbacaaacaacaaabacaabbcacbbbcabacbacaaaccabacaabcaccaabaccabcaacacbcacbbbcaccacabbaaabcbacababcaaaacbbaabccbaacaacccbbaaccbabccccaabcaaaaaccaabcabbcbacbbbbcabcccbaaabcbabacbccbaaaccaaaacbabcabbbacbcaacaacbcbbcababcbaaccababaacbbaacbbccabacabcbbcbacaaabbacbbbcabacbbcbaacbaabbaacbaaababcbbbccbaaaacaaaccbbbaccbbcbbcacbbcabbcabbccbccbbbaccbbcabacbcaccabccabaaabccbcbcaabcabbbbcccabaccbbcccaaaacaccbaabbbcccabbaaabcaccacbbaccaccacacbcbcaabbbbacbccabcabbacbcacacacaaccbbacbbccbabaaabbaacabbabcbaacbabbcbabacabbbcbacbbacacacaaababcaabacbacacabbcccbacbbbbabcabcacbccbcaaaacccccacbbacbabacabbcccbccbbaababbaacbcccbbbaacbaabbcbacacbaacabaccccbaabcbacbbaabccccaabbbbabcababcacbacbcccaababacccccbbacbbbcbcabccaacacbbbbbbbbacbbaabcccaccccabcaabbaaaacacbabbaacbbbbcbcabbacccacbcbcccbaabacbbaaaaccbcaabbbcbbbabcbbbccacbbabaaacacaccbabcbbcabaccccbbbabababacaacccbbabcbcacbcccaabacbcacaabaaacccbaccbabcbbaacaccaacccacccbaaaabaaabbabcaccabbbbcccbbcaccccabbbcbcbcbabbbcbbaaaccacccaccbcccabbcbcabcbbcabcbacabababcbbbccaabbcbbbaacabbbccacabcbacbbaccabbbbbbacabbabababcbbcccaccbbbabcbbccbbccabccccacbbcbccbaabcacaacbaccbbabaacbbabbccaabacaacabbabccbbcababaaccaacbcacbcbcabaccbbcacbcacbaabaccabcbbabbaacacaabaacbacbcccabbaaaabccabcacababbcabbcbacccaacaaccbaacbcaacbacaabcbbcabaabbacaaabaabcccccabbaacabccbcabbbabbcbcbabbaabcaabbbcbababcacacccbccabcccabcbcabbbccabbbacbbccaacaababbccacacbbababbbabbabcbcbcccabcaccaaabacbacababcbaabaabbbbbcccbbccabaccaaabcacacabacaaabbcbcbaaccabacabaabaabbbbcbabcbaacacabaaabacbcabcacacbcaaaabbabaccbcbaacbcccaccccbccbcbcaccaabbccbbcbabacacbccaacaccabccbbcccccbcccbbabcaccacbbbaabccacbaaabacbccccacbbabcaaccaccbcacbacacabacabccabacaacacabbcacabacccaabcacabbaaaabbccbababbbcaabccaacabccabcccacbabacaccaacaccccbbbcccbaaccabbcccbbacaabbbccbbbaabcaaaacbabbacacabcaaababbbaabaacabbbcbababbbcaaccbcbbbbacaacccabcacbaaaacacbaccbabcaabaababcbabaaabcbacbbbcacbbbaaaaaabbacabcccbacbbbaacbbacbaaaaaaabcbabaabcaabaacaacabccbcccbbccbbccccacabacaabcaabcacccbaaabbbbbbcbabcabaaabcbccbcacaaccacbabccbbabccccbaabbcacabbccbbaacbcabaaacbbccaaaccaaabbccbbacaabcbacbabaaaaabccccacaabccbabbaabbcbbacccccaccbbcacaccbaaabcbbabaabbabcabcbbbcacbacababbacbbaccacabcccbabcbbcabaaccbabababacabbaaababbbacbcacbaacabcaacaaacaacccbbaccacbcbbccbaaaccaaaaccbcaabbbcccbaaaacbcbcaaabaaabbcaaabbaccbcaaacccaaccabbcbcbcbbacabaacbbaaacbcacabacbcbcacaccbbcaccccaabcbcababccabcaacabbbaccccbcabcacbabccbbababcbbbcabbccacaaccaaacacabcabcabcbcbbbabbabcbacabaabacbcccabcabbabbbaaaaaaabbcacbcaaacbbacacbbbbbbabccccbbccaaaabaccbababcabcacacaaabcbacabaacacabbaaaaaabcaaccbccbbbbacacacacccabbbacaccbbbbaaaacbbcabccabbccaccbbacccbbabcbbccaccacbcbbcbbcbbccaaaccccbcbabcaacbaacaccabaabaababbaacbcbbcccabbccbccabbcaaaaabcbcbcccbcabbaccccabcbcbcccbcabccbacbcbacacaaccbbacbbaccaaabbbcaccbaccbbbcaaaacbcabbbbbbacbabccbabccacababaaacbaaccabbaccbaacbaccbabacacacacccbccbbcaacbaabccabbbbabaababcaabaacabccaccbbbacbcaccaaacababccaaaccbbbbacccbcaaaababcbbacbcaaccccbbbbbbccbcbacaccacbbcaabbaaabbacaacccaaccaabcaaabbccccbabcccbacbcccbbacaacabcabbbabbaaacabbaabacccacccababacbbacbbcabbcbcacacacbbccbacbacbabbaacaaabbcabbccaaaacabbbccbccbaacabbbaababbbabaabbbbaaabcacaaaccabcaaabbbbaaabcacaacbcabbaacbbbaaaabbcbcbaacbbcccbcbbccbaaacacccaabbbabacbcccbaaccccbbccabaccaababccbaabcacaaccccbbacaacbbabcbbacbbbaaabcacbaaccaccbbacabaaaacbcbabbbabababbbbabaacbaababbcbbabbabcccbbbcaaabacabcbcaaacbbcbbaabbccccaacbabacabacbbbbaaabbbabbbaacaccabcbabcabcaabbaccbacbacbbbabccacacaaabbcbbcbccabcbbaacaccbaaababbbacbabccbabcaabbbaaaaabababaaabaaaccbbaacaccababcbcabcbbabbbcaaaaaccbccabbbbabaabbcacccbbbbcaaacbaaabcbcbbacbbbcaaaaacacbbbabacababaabcccaababaaababcbcbababaacaabbacbcbcaacbccabcccacccbcbaababcaacbccabacbbabacbbccbaacbbbbbbabbabbccabbcabccabbacaabcbabaababaaacaccbaaabaaabaaabbcbbbacbbaaabacabbcbaabbccaabbbacbbcbcbcaaabcaacbccaaccaaacbacccbbcbbbccaaacaaacbbaacbcbbccbccbbccbcbcacabbaabaaaacacabbaaaaabcbaaacaacaabcbbbbaabaabccabcaabcbabaccbaaaaabacbaacbcbcccacccabaaccaabaabcbbbcbcbaacaacbcababababbbaaacacabcbcaabcbcbcbacccaaacbbaabaacbcbaabcbcbbcaabababcbcabbccbcabacabbbccabcaabaabccbacaacaccacbccaacabbaaccacbababccbcbabaacbbcccbcaacacbcbcacbacbcbbbbbbcbaccacbacbaaaaaacccaabbbaacbbcccaaabaacbabcaccaccbaaaaaaccbcccaabcccaabacbbcbcccbabbccccaccabaaccaccccbabbbbbaabbcacabacbcccabcbacbbbabaccaacaacbaabcbcabbabaaabccaacbabbbbabaabaccbacaaacbbcbbcaccbacacacaaacbcbaaaacacacbacaccabbabaacbcccbcbbccaabacccbabbbbaaaacacaacccbbacccabbbbaccaacbbbaacacbcaccbbaacaacbabbbabcacabaabccbbbccaabacbcbbababacccbbabaabccaacacbabcbabbccabaabcccbcbbbcbbccbccbbcabcaababbbbbaabbbbabcbccbbcbaababbbcbcbaaccbcaccbbaaccbbacbcbbcabbccbccbacaacabbababccacbabbcaabcbabaccacbcabbcacacabaaccaccaaaaaccccaacbbcbcbbbabbbbacbbcacccabbaaaabccbacacbbcccbaccbcacabcbbaabbcbcbaacaaabbbbacaabacacabcbacaabaaabaaccabaabaacaacacccabaccaabccaaabcbcbbcccbbcabbabccbcacccaabaccbbaaabbbaccaccbaaabbabbabccbbcacacbbacbaacbcaccbaaabcabbacbcaacabaacabacabcbacbbaaccbaaccbccaccbbccaacbabaaaabbaaaaaaaccbcccccbacbcaaaabaabbbabbaacbcbccbacbbbbccbbacccccbacacbacbbbbaabaaaaabababcbbcbaacbcaccbabacabbcbbccaaaabaaaaaaabaabaacabcbaaaacbaabcccccaaacaabcaacbabbabaaaccccbbbaabaaabcabacabaccbcbcacbaacacbbbcabaabbacbbbcabaaaaabbcbabaaaacbaacbaccbccbacbacababaaccacbcbccbbacacbbbbcbcccbbcabccbabbcbcacccaabbccbcacacacabbcabcaaccaabbbbcbbbcacabccacaabcaccbaacbbacabccbbbbbcabaccbbbcccbaaccbbcbbabcbababccccbbccccabaccaaaabccaacbbacccacabbccabcabcbcccbcbabbbababaaccbacbabbcaacaacbbaacacbaacababccbcaabcccccbacbbcaaacacccccacbcacbbbabbbcbcbaccbaacccccbacccabaacabbaacccccbaababccbbbbcaccbbbbbaaaabcbabccbbaaacabaaccbaabcbccacbccacbcaacbaabcaaaaacabcbbbbbabcaabcaccccbbcaaabcaaabbbacabbbbbcabbabbbcbacabbbcaccccccbaacbbabbcaccababcbbbcabcbcbbbcabbccbacacabcbaacaabbabcbcbaaabcaacbaabcbcbbabbaabaaacccabbacaccaacaccacaacabaaaabacbcabbcbaabaaaccbcbaccbbacbabcbbbaccbbccaacabcabacabbbccaacbcaaacbcbbbcbbaabaabbbcaabbaaacbabcbbcbccbcabcbbbbaccaabccaccccabaaaaabaabcacaaacccbccacccabaabccbacacbbbababcaabaaabbcbbccccbccabcbabbbccaabacabacbcabcccaaaacbabccccaccabbabcabcabcbbccaaabcacbbcaaabccbacbcabcabaabbbbcbabcbbabcacbbababaccaccacccbaabbbabbbababaaccaaaabacaacbbccaaabaacaacbbbaccbcbbcbcacbacacbcbcccccccaababaabcaaccbcabbabcabbabbbbbbcbbccbcbccaabababaaaabaccbbcababccbbabbcabababbacaacbbcccabbcbcaabbcaabcbbccbacbbccbcbbaabbccbabccacbbbaaaabbbcabcaabbccaccccaaccacacabaacabcccabbcbbbbbacbacacbacaaccacacbccaaacbcacbcbcbabbbabaaacbccbbbcccaaabcacbcbabbaaaccbabacaabccbaacbacaacacabbbccbabbcbaccbcaaccabbcbbbbaccabaabcbacabbabcbacacbbabaacccccbcbaabababaaccccaccbcbcaabcaaccccbbbbacbccabccbacccbcaabbccacccaaabbcbbbbaacbbabacbbcccaccabacabbacccbaacccaabbcbaccbabcacccaaacabbbabbbcaabccbcaaccacacabbcbbabbbabaaaaaabacaccabcabbaabacabccacbccccbcaabaabcbaabcbaaaaabccbacbbcbbccaabcccabaabbaccbcccabacbaacbcacabbccababbaababbaacbaabbacbcaababbcacbcbccacbbcaaaacabaacbbcababcacbacbbbccbaacaacaccbabbccacbaabbbbbcacbaacacacccbaabacabccbaaabaccaacbabbacabcbbccacbaaaababbbaccabcbacabaacabccbbaabacacccacacbcacabbbbbbccccbabaababbbacbbcbacccbaccaaccbbbbbaaababaabbccacbbcabaccacbbcaaacbcabaacbcabbccababaabcbacbcacacccaabaabbaaabaaaaaacccaccbcccbcbacccbaacbacbbcacaaacaacbbacabaccacbbcbcbcbabcbcababbcacbbcababacbaacbbacabcbcababbcacabbbacbccbcabbbbacccbabbcbbcbccbababaabcacbbabcabccbcbbaccccaabbbbcbbcaabaaaabcbbcaacbcbcaaacaababacacbcabacbbaacaccbbbbacabcbbbacabcaaaaaaaaaabbbacbabaabaaabaacbabbbcacababcbaacacabccaacacacabaccbbbcabacbcccccbccacccaabbbabaacbcabcbaacabcaababaccaacbacabcbccacbacabaccccbcbcabacabcacbccbbabbbccacccaaaacacccbbababbcbbabbabaacaaaaababccabababbccabcacbcabcccbbbbbbcccccbcbcbcaaaccabaabcabaacacbbcacbabbacbaccbacbaaccbaaaabaabccccbccaababcbcabccaacbabacaacacccabaabbabcccbbaaacabaabaacbaacbabbcbaccbcbabaccbcbcbcbcbbaabccbcaacbbabacbaccbababcbbbccabaacaacabccabcaabababaaacbabbaccaccccbcabbaccabcccbacbcbcacbabccbaabaabbbbacabcabccabcccaaacccccbbccaabaaccaabcabcabccaaaababcabccabcbbaaabaaaccbccbcacccaababcbcccabaaacaabcccbcccaaaccccaaabaabcaaaaccabcaacabcbbcabcabcaccacccbbccaccbbbbbcbccbbbbababacbaabcbaaabcbbaaccccbbbbabccaabcbcbbcababcabcacabacbbcaaacbbabbcbcabcbaaabaaabaacbaabaabbcbbababababbbbcbbaabaaacacbbabacaaaccccacbbbabbcbacaccaacaabaaccbbcccaaaacccacbcccbbcbacbabcababaacbcbaaacccbbaaacabbaccaccbbbbabaccbbbbbacabaacbacaabcbbaccbbbaaccbcccacbbacaacacbbbbabcabbcbaacbbbcabaacbacaaacabcccccaccbcababccbacbaabbcaccccaacbbacabbabcbabccbbbbcbacaabcabbabbaccabccccaabbccbccbabbccbbcbbabbabcaababcacbbcccaaccbbaccccacacabcbbcaccacaabcbbcabccacababaaabbacbcaccbbaacccabacbacaaccbaacbaacbcccaababbaccbabccabcbaccbbccaacacaccaabbbacbcccbacbaccaabcacacbbabbabbbbcacccbabbcabbbabbaaccacaccbbbbccaacbcaccaabcbcbbcbaababcacabcaaacbcaaaacacacacabcbcaaaababcaaaabbabcbcaaccbbcbcbbbbacacaaacbbabbbbcccccaccbabbcaabbabcaabaacabcababbabbbabaabcbacaccbcbcbbabbbbccbaaaccbcbbaacccacbbccbbbacbcaacabbabcabbcccababccbbbbccaabacacbababbbaaaaabbabbccabbbbcbccbbaacaacbcccccbccaaabbbcbaabcccabbbacbbccbabcabacbbcbccbbbcaaabbbacbaabbbcbbbbababaabbabbccacbaaccaaaabaaaabaabbacccccbcbacaabaaaccacccababcbaabcccbcaacccaacccbbaaabcbaccbccbcabcabccbcacbcaabccabaacccabcbccabaccbcbbbbbbcabcacacccbabbcccaabcbbccbcbbcbcbbbacacccaaaabbbabababccbabaaabaacacbcaccaaaccccacaacacbacacbbbcbccaabbaabccaaaacaaacacabaabacacabbaaabbaababbacacbcbacacabaabcbacbbabbaaabccaaacbbacaaccabbbcacbbaacbcbacabcbbbccbcbcabcbcbbccbacacbcbaacbbcaaaaaaacbbccbacbbabbcaacabaabbcaacababbaccbaabacaabbcacccaaaabcaacacacacaaabbcaccabbbaccaabcbcaaacabbaccbbaabacaaaccaabbcbbabacbbbabacacacabcccacababcccbacaaabccabbcbbbabacaaccccbcaaaccccacbabbbaccbbabacaabaaaababbabccbacbcbbccabbacbbcaccacacbbcacccaabbccbaaabbaaaccaaacaaccbcbccccbccacbcacccabaaccaabbcacbbababababbaabcbbbacabbacacbcbaaccacaccabbcccbbabbbbbabcbaacacbcbabcaaaacbbcbcabcabbabaccbbcacbacbbacaaccaacccbbbbcbaccbcaaccbbacbbccbccccccbbaacaaaabcccbabcaabcaccbcaccaaaccabbcbbacbbcbcbcabacbcacbabaaaccbabacbbcaabccbaacabacabaaacbaccccababcabbabaaababcaaaababbccacbccbacbcaacbbaccbbbabbcbabbcabccaaabcbbbbccbabcacabaaabbacbbbaaccaabaabccbccaacbabacbcabcccaabccbcacccaacccacbbccaacbacaacbccbbabcbbbbbaaccbbcbcaababaabababcaaabcaccaabbcaaccabaacbcbcaccbaaaabbaccbbacbbabaaabcccaccaaccbacbbbbabbccacabbabbcbbacbacbccabbccbaaacabcbcaaccaabcaccaabcbcbbcbacaacbcbcbbccabacbaabacacbbbabbbbccacaccabbacaaabccbbbababccbacaabbbabcaacabcabbcccbaaabbcacabbbbcccabbccccabbabbabacbbcacabbcaccaaaaacbccbbaccbacabaccbbcaabbcbacaabbccacaccabcabbabaaabcaaccbabbacabcacaabcbabbcbbbbabacccaacbacbabaacacbbacabcaaaabcaacacaaaaccbbbbabaaacbcbbacbababccbcababcaabbcccbabbbabbbabaabcbcabccccacbbbccbacccacaccccacccbaaabcbbacaabbcaccbacccbbaaaabaaabbcccacbcbaaabbbbcacabbbcacccabaacaaaccccbccacccabbccaccbcabcabaabcccbbcccaacbabbcbbbccbbbacbccbaabbccbaabbbacbbbbaccbbaacbcccccabbcaaacaacabcccccbbbbcccaacccccccacacbbbaccbabcbababccbaccaabcbaacaacacbbacbccacbabbbbacaaacbbabcbcabacbccbbcaacbacbbababaccccacacacbcbaaacbabbabbaacbcabcbcbbcaabacbbaaaacbcbababaacaccbbbbaccaaabbabcccccbacabcabbbccccaabaacbbcbaabcacacbabacccbcaaaababcbccacccabbabacacabbabacacbcacaccccbaacbbbaacbcbaacbbacabcabacbaacbaacbbbbbaacbbababcbbccccacbcbbabaacbaacbabcaaacbaacbabbbbcbaabaacbcbaacabbccbcbcbccbabcbacbbcccbcaacbcababbabbacabbccabbaabcccabacbbbbaaabcbbabcabccbcababbbbbbbcacbcabcccccbcabccccaacbabacbbcccbccaabcbcbbcaabacabbbbaacbaaaabbbbbaabaaabccbcccbbbccbbacacbbaaaccabccccaacaacacccabcbcacabbcbbbacaabbbacabbbaacbccbcabcccbacbacbacacbcbaabbcccbacabbbccacccccccbbcbaaabcbacbcacaabcbacccbbabccbbacbacacbcacacccaaaabbbaaabbabcbaccbbabaccaaaaccabcccbcccbcaccaccabbbbbcaaacbaababaaccccbccabaacbabbbaaacbaaaacccccbcabcababbacabacbcccaabacccacbacbcaacabcababbbcccaaaaabbaccaacaaabacbbcabcaabcaacbaaccaaabbbaccabbacacbaabbbbbcbaaabcbaabcbaaccabcbbacacbacabcbbcaabbbaaacabcbbaabbbbcbbbccbaaacccabcbcbbbabbbaabbbbcbbcaabbcaaacaabccbbcccaabcacbccbbbbbccaacccbccbbbacccacccabcbcbcbbaccbbbaacbbaabbabbbbbabbaabbbacbbbcabccaccbbbcacabcbbbacabcbbbccbababcacbabccabbbabbccbbbcbccbcaaabacbbbabcaaababccaaaaaaccabcaacabbccccacbcabcaacacbbbcaabbbbbaaacbaacabaccabbcbaaaabbaccbcaccaacaabbbbcababacccaaabbabbbaaaccabccabbaccacaaaaacaaaacacababccbaaccbcabbbbaaccbbcbaaccbabcaababcbccacbaabbcabbcccbccbbbccabacaaaaabbababcbbaccbcabaaaaabbabbabbacbcccaabaabaaababbbbabbabccbcacaccbcbbaacccccaccacacabbcbbcccaacaaaabaabcccbbbbabaabbcabcccbbcaaaacbbcbbbbabbbacaccaaccaacbabcaaababcbacacacccaacbbacabccabacaaaacbabcacbcabcaaaabaaaaacbbbaabbcaabcacabbabacabcaabbcccccbbcbccbbacbcaabababcacabaaabababbbcbcbbcaccbbacccabcabcacacaababbaccccacbbcbbbbcaacbcaacbbaabaaabbacbcabbcbabbaacaaacaacaccacbcbaabcacbcaabcbcabaacbabcbaabbccaacaabacbbacabacbcbbbabbaaaccbaaaabbbabaaaabacccabbcbcbaabcaaababcbacabbacbcaaacccccbcaabcbbbcbcccbbcacbaaacaaccbaabbbbaccbcbbbbccbcaabbccbabaccbbcbbbbababbaaaccababcbccaaaccccccbacbccababaacbcababcbcbbbbcabacabcccbacccbcccccabcbaacbbaaacbaaaaacabcbbacaaabcbbbbbbabbacbabbacaacccbbababbacacbabcbcacccccabbbabbcbccaabcbcacbbabcbbacbcbbcabbcaaaabbcaccacaabacabccababcbacaabbcbaccabbaacbbccaaababbaccbaababcbbacbacaccbaabcbcbbabbbcaacbaaaabcbccbabbbcabbacabbbcabbbaaaabcacccbabbaaaccacaccbbacaabaccccaacccaaabaccacaaccccbbaaacaabbacaabacaabcbbbabcbcbbbbbcbcbcacbaaabbbcbcaccaccbbbbcbbabcabaaaccbaabcccbcbacacbbccccbacacbbaabaaabcabaccccabaaaabacbaacaccbcbbcccaaaaabbaaaccbcabcbcacbaccacaabbbbcaccabcaaabccaabcbcacbccccccbacacaacbaaabbbacabbcbcbcbcbacbaaccabcbacaaabbbccbcbccacbcaabacbcabbbbbcccacbacaaacccacacbbccccbbcabbaacbacaaaabbbaccbaccbbaabbacacccccbaaaaabcccbabacaccbacacaacbbbabbccccbabcacaccbbaccacccaccbabaaabcbcbccaacabbcbabbbccbababcababbbabaabcbacacabcccbcbaaaacbabaacccaaccaccccaabaabbcbcbabbcabcaacbabcbaaaccabcbaccccbaacbccbababbbcacccbbabbcacabcbbacacccabacacbbababcabcccabcacbacbbcaaabababcabbaabccabccbcabaabacbcbaabbaccbcbbaaabaacbbbaaacaababcbcccabacaabbcccbaccacaccacbacccacbcbbacbbbcbcbcacbbababbbbcbaccbbaacccaabababbbbbabbbbbbcccbcbabcababcabacccacbacacbbacbcbacbaccbabaaaaabaababbbbabbccbbabcbbccabaababcacbcaabaccacbcacbabacaccbcaacacaabbaabbcbccccaccbccbbababbcbaccbacbaaccababbbaacaaccbaaacccbabcaaaccccbcbbacbacacaccababcaaacaabababbaaacbbccaaaaaccabbbccbacbacabbaacbbacbacccbabbbbaccacbaababcbbbbcacbbbcbbcabacbbacbbacacbccabcbcccbbcbbbabbabbbbabacccabacccccbaaabacaaaccbaccaabacbabaccbbaacaccababacaaccaaacbbbbccaacccbacababcacaacbcbacccccbbbcbcbccacabababcbbcbaabbabcccbaaccccbacbcaaacabcababcbaaacbbcabcabcbbabbacbbacacccbcbabbcaacabcbcaabaccbacacaabbacbcccaacbabbcbcaaaaaabacabbbcbcccbbaaabcaacbbacccbacccaacbabbcababcbbabccabbbcccaaccaccbcccbaaabccbbccbaabccaabbbbcbcabbbbaabacaccbabcaacacabaacccbbcbccbbcacccaabaacccaaacacbbacbbcbcbabccabaccaccaacaaabcccaaacbaababbccbcacbaaacaabcbcaaabbbccacccbaacaabcaacbbabcabccccbbabbbccacbbcbbacbaccaacaabccaabcacabaaabccbaaccaaabaaacbcccababbbaaccbcbcaacabaaacbaacccacbbcbbccbcabbaaabccbbbbbacbbccabbcacccbccbacababbbbbbaabbaaaccacacabcbcaaabcbbabbaabbbbcccaacacaaabbcaaaabbcababacaabbaacbcbcccbbaabcbbbbcaaaaaabaacbaacabaabccaacaabbccbbcbcbbaccbaaaacaacbcaccbbaccacbbbcbaaaccabbbacaaaabbbbccaacabccacaabbccaccbcbbaaaababbcbbbcbabbaabcbbaaabcbcbbaccaabaccbcabbaabbccbbbacccabacccbabbaaabccccbaaabcaaaabacccacacbcaccbcbbaccbbcbcbcabbaababbbcaaaaabcccbcbbaacaacbaaaacbaaabaacbaabbbaabcbccaabbcbcabcbbcacabbaccaccabaaaacbcbbccccaacccabccccababcacbacbbaccbcacabcbccabaaaabcbccabbbccbbacccabbcbbabbaabccaacabbaaacccbcbcbabbbaacbbbaaccaabbbbcbcbcbbccaccabbaccaaacbbcbabcccaabacabbbbbaaabcababcbabcccbbababccccabaaaabbbbcbaacaccacabcbaabaababacbbcaccbaabaccacbbbcabababbabcccabbabaaacbbbaabaaacacbcbabcbacabaacbabbabbbbcacbcacaacacbcabacbabcaaaaccababccabbaccaaabbcaacaabbbbacacaaabcccbbaccccbccacbbaacbabababbacacaacbabcbbabaaaabbbacbbcbbbabacbcaccaacaaababaaacabccaacbcabccbcccacaaabbbcaccbccaccbcbbababccaabbbbabbbbacccbccababbaabbaaccabacccbaabacbaaaccaaaccccaaabccccaabbcaaabcbaaaabbaabcbacbbcacabbaacbacbbbaabaacaabbcbbbcbbbababacbbcbabbaaccbabcabbaabbcaaabbcbaacbaaaaaaabacccbabaacccbbcababbbabcabaacaccbccacabaacaaccccbabbcaaaabacaccccbbccccbcacbbaaccbaaacbbaababaacccbaccbbcbbbbacbabacababacbcbbbcbbbaaccbaaacaccacbaaabcbbcccababcabcbcbbacccbbbbccbbccbacabbaaacaabaaaccbccbcbaccbcaababaababbcbabbcbcbcaaaaaccaacaabaaabacacaaccbbabacbccbbaccabcbabbabacccccaacaaaccaabccbbbabcaacaacaaccbbbabbbaababacbaacacbbbcccabbbacbcbcccaababbbccccacccccaacbacbcababcaacabcacaabcbccacaccccabccbacaaaaaaaacacaacccaabccbbabaabcababacaaccabccbbababcaabbacaacacacaabaabcccbccabcacbccacaabaaccbacabcabccaaabcbacabbcabbcbaccacccaacabccbcabbabaabbaaacaaacabccbabcbaabcabcbcbbcaaabcccbbbcccbacbccaabbcbbabcccbaaaccbccbccabababacaabbcaabaabccaaccbcbaccbbaaacababaaabbaaccaccacacabaacacbbbcbbabacbbbbbbccaaaacabbbcccacbcbcabbaaccbbaccacbbccbcabcaacabbbbacbcbacbbaacbbabcbbaaccbbcbbbccabbcbacaababbcabcaccbcaccbaaccbacaabcbaacbaacbbbcabccababccacaaabaabccaacbbabcabaacaabbcbccbbcbbacabccbacaabbbcaaccaccbccbcaaacaabbcabacbbaacbbaccabcaccacacacbccabbcbbaabaacbbacabaababbccccbcacaabcbbbcbabcacbbabcbbacacacbccbaaabbaccbaabcccaacbbbcbbabcacbacbbbcbaabbbacbbaaaaacacabccabcbcbacccacaccccabababaccbaabaabbcacccababcaacaacbcaaababbabbccabbcccaaccaabaaaabbbccbbbabacabcbcccacbbbabbcbacaabbaccaabcacbbabbbabccbacaabcbbabcbabbbccaabcbbbcacaccbacbcacabaccbcabacccbbbcacabbaabacbbbcacccaabaccbacacbbcbcacbccccabbcababaacacacaabaaabbbcbabcbbccababcccacaccaacababcccbacbccbcacbaabaababbcaaacbabacbabaaccacbabbabcbcacababcbaabcaabcabbabbcaacaaabcbccacccbacbcacaaabbbbbabbaaabaacaacbcbabacacbbccbbbcaabccccaaccaacacabacaacaacbababaccbcbbacabcabcbcacbcbaaacbcbcabcaccaaacbabaccccababcbcaacacccbcbabcbccaaaababbabcbabccababbbacbabcccaaaaaccababcaabccbbabbbcacaccbbaaabbccbbcaabcbcacbacabcaacacbacacbabcbbbcaccaabbcabbbcbcbbbccbabcabbacbbccbcacaaaabcbacacbaaaabbccaaabcaaccaccbacccccbcccacccccbcbbbabbcabbbcbababcabbbaabccbbbcbabbccaccbacaacababccbbcccbacbbabbacbcccbcbcacababcacacbbabccabbbbbcbcaabbaabbccbccbccaccccbbabbacbabaacbbacbacccbaaaacaacbbaabacbcbbacbbaabbbaacababcbacacacbacabcbabcccaccacbcbaacbbacacaaaaacbcaaababbbccbaaacbcaacbcccaaabbbaaabababaccccabacbcaaabbbcaccbbcccacabaaccccbaabcabbcaabaacaabcbbccbcaccabacbbbbacabcbbbabaaccbbaabababcbaacccbbcbcccbcabcaaaacabbaacacbaaacbacbccbabcaabbacbaccccbaaccabbaaccccbacbacaccacaaabacbabcaabaabbbacaccacbbaaaacabcbabbbcbcbbaaabbabccccbbacbcabbacbccacabcaabbbcbbbbcbabccbbaaccabcaabbcccbbbcacabbaccbccbcbaccacbacacacbcaababcbacabccbbcabbbacbcbaaccabbcccaaacaabcbabcabaabaaabcaaccbacaccaccaacbaabcabcbbaacbcacbacaaaaccaccbacaccbbcabbabbbabcbbccccabbcbbcacccacccbcbbbcbbccbbacccabccbbccacacaabaacbccbbbbacacacbbbbcbaabccbbaaaaccacbbabcacabccbcbbaccbcbbccbbaaccbabcbbaaccbbccbaabaccbbbaccccabbcacbbbccccbcbcbbbacacacbabbabaccbbabbabacbcccbabccacbaacacbcbacbcbaaabaabbbbcbbabaccbbacccbabaabcaaabbccbcbbbcbbcccbbaccccbaabcbbbacaaacbbcbccababacccbabcaaaaacccbabcaccabcaabaccbbaabcbacccbacaaaaaccacacbcaabccbaababcabcbacabbaaabaacbaabcbcacaccaabbabcbaacacbacbbccacabbbaccbaaacbacbabaccbaaaccbaacabcaacccaabbcbabaabaabcabbabbcbbccaababbaaacbbacbaabbccbaabbbcabbccbacaababbabbcbbbaabcccbaaaabaaccbcaabbbcbbbaaaaabccabaabcbacacbbbccabbaaaabbbcaaabbbaacacbcabacacbccbbabaaabccabccbccccbaabbccacabbccbccaaabcbccacbcbabbabbabbbccbababcabcbcbcccabbbabcbbcbabaccbabbacbacbacabbbccacbbacabbbbaacabbbbabbbcaaccabcbcbaabaccabccabacccbaabcbcbacabbccaaabaacaabbaabcbaacabbbabbcaaccabcbbbbabbbbcabbaaccbcabaaccbcabaccbcbaabcbccaccbbbcacaccbbaccbabacbabacbacaacbbaaabbabccbaabccabaaacaabbcccbabaaacbabbbaabbacacbbcabaccabcbbacaccbcbbccbccbbccbbabbbcccabbacaabbcabbbcabbccbcabbbcbcabcabcbcbbaabbabbbaabbcccbcabbcacaacacbbaaaabacabbcababcaccbaaccbaaaccbabcccbccabbbabbaaabcbbbbcabbbbacaacbcbcccaabccbbcbacbbcbbbbbbababcbccbbbcaaabbbccbaacabcabaaaabbbbbabcbababccabaaaababcacacacacbaaaccbaacbaabcaabaabcaacccabbbaabcaaabbaabbaabacabccabbcabbaabcaaccaaccacbcbccaaccbbaccbbbbcccbabbbbbaacbcbaacbcbaacbabaaaaaacabbabaacbbcbbababcabcbcababbaabccacbacabcbcaabaaaacbabcbbbbcbaccabaacaaabccabcbaabaaaaaaaacccbacbbcabbbcaccacbbbcabbcbbacbaacbaabcaabbaaaaaacacabcaacbcbcaacbbabcccaccccabcabcccbbbccabccbaacbcbcbbacccbacbcbcccbacccacbbcbccaabbacccaaabaabbacccbacbcbabcbabaaaabbcaabccccaacacbcacaaaacbcbbaaacbaacbcaacccbaaaccaccbbbabbacabcacabaacaccacaaababababcbbcbbbbaccccbcbcabaacccbcbcbbbacbcaacacbacbacbaababcacaacacabbbbbbccbccbabcabbbbbbabaacbaaaccabbccabababbbcbbaaccbbbaacabbaabccccabbccaacabcbabbabcbabbcacabaccbbabcbcaabcbbcbcbaccbacccabccbababbabacaaacbaccabacaaabccbcbccacbcaababacbababcaaacccbbcbcaaababacbcbbbacbabacbbccabcaccacabbcbaacbcaabacaaaabcbbacaacbcbabbabbabbbacaaccccccacbbaabbbcbacabaaabbcabbaabbacccaabccabbbbbabbabcaabbccabcbbbabaabbcaaababaaacbcaacccaababbabbaaabccbaacbbaabaacccbacccaaaaabbbaccabcbccaabcaaabcbcbbaccabacabcbcbbbabcaccbbabcbababcbbacccbbabacacbaaaaaaccbaabbcacccaccbcabcaaacbabccbacacbabcccbcccbbbaaaacccaaaabbcbbbaabcbbccccabcbaaacacbabbbbbaacbabbbaacacabcacaccaacaaaccbcbbacbcbbaaaabaabcbcaccaacccabacbccbbbababbbaccccaccbccabaacbccabaababaacaccacccbabcbcaaaaccbcbbbababcaaaabbcabaabacccabcacccbccbbcaaacbabbabaaabaabacbbcababaacccbcbccbbaabbcaababccbaccabbacbccaaaababbcbcabcbcbbbabcccbbbababccbaacbcabccacacccbbcabcbcacabcbbaabbbaaabcbcaccacbbaacbaabbbbaccbcacbabacabcabcbaabbbbaaaaabbcbbbbcabacccbccabacabcabbabaabccccaacbbabaabbbaacacbabbbbcbcacbaaaaacacccbcbccabbbaacbccbbacacbbabcacabaccbcaabaababbcbbccbabbcbaaaccccbaccbccacbccaacbbbbaacabacabcabcbccbabbcbaacaacbaabaaabbabccaaaaabacbccbbbcaaacccbaaacababaccbccbaaacabccccabacacbbcaabacbcabcaabccccacccccacccccbbabccabbaacbcbbaabcaaaccaabcbbcbaccabccacacbcaaaaacaaccacbcccbabacccacccabaabababbbcaaacabbcbaacaacaabbbcbaccbaacbbaabacbbccbbacbcbbcaaaccaccacabacacaccccabcbcbcccbbacabcacabacbabbcabcbbbcabcbaaaaabcbbbbbcbabcacbbcacbcaabcaacaaaaccccabbbcaacacaaacbabaabccaaccabbaabbcaaabaccbabbcbbccabcbbabccbcaccbccaacababbbabbcaccababcccacacacaababacbbbacbbaacbabccbbbccbcabcccbbcabbcaacacccaabccccbbaacacacaaaaaabaaaacaabcaabcccbbcbbbcbcbbcababcacaaacacbbbcccbbccccbbacccaccabbabababbaaacbcbaacbaabaccbbcccccabbbacccbcbbabccccacbbccbbabbbbacccbaabaababaabacabcaacaabbcabacbaccabccaabccaacabbcacbacbccbaaccabccbcacbbacccaccaabbbbabcbcacbabacbaccbaaabaacbcaabcbbcacabcaabcbcaccccbbabcabababbbcabccaabcabcabcbcbccaccccbcccaabbbcbaccccbaccbbbabaaccaccabcacbabcacacbbbaaaccabbbaacaabacbabcabbcaaabcccbaaababacaaaaccbbacbacbccbabaacbabbbbaccabbbbbcccabbbacbbbcbbcaaacccbbbbbcbcacbbacaccbacccccabbcaaaaacaaacccbcaaccbababccbbcbcaabcaccaaabcaababbcaccccccbbcabbbaaacbaabaabbbcbabcacbcacbabcccacbacbacbbcccbabbacbbbbbbbcacccccccbcacbbacbbbabbbcabcaabacacbbbaacbcbababbbaaaababacbbacabbcabcbaaccbcabaabcbbcaccabbacbcccbbaacbacabaccaacaccabcccaaaaabaaccaaacbaccacaabcccaccbccaabbacbcbaabcaaacbbacbcbacbccacabcbbaaccbcccacacbacbaaacbababbbcccbbbaababbabcaabcbaaabcccabbbbaccbabbbaabccbabcbccbbbbccbcccbaaaacbaaacaccaabbbbcaabcccccabaabbaccababbcaccbbabaacbcbbcbaacabcaccbabaacbbbbaacbbaaaccaaaacbccbabaccbbccaabacbbacccbabaabbbbcbcbccbcbcacaaabcabcabcbcccccccbaaccbbaacabaaaacaacacbabaaccbcccabcaabbcbabacbabaabcaaacbaccabcabbabbbababccabaaabcacbaaabcbbacbbcaacacbabacbcaacabcccbcccccbabacbaacbbacabbcbbaabccbcabacaaabbabacbbacbaacacacaaabcbacbabbabbaabcaccccabccccbccbbaccaccacccbcacbbbacbcababcaccaabbcbaabcabbbcaaacacacbbbabbabbaacaacbcacbcbbbabbccaabccaaaabacaabbcbbcaaabbbacbacaaccbabcbacccbbacbcaaabccacbccbbcabbcacbbaababacccbcbcbabacacacccacaaabcabbccabbbccbcbcbcbcbaaccaaacaaabccabaccabcbacaaaaabbcbcbaacacbcbabcccbcbbccccbcaabaabcacbcacabbcccbbaabbaabaabcbcccaaaaabcababccacbcbaabaacacaacccbacbcacbbbbbbcacccbbbbaacacbcbcbacbbcbbaacacabcbcbcabcaaaabaaccbaaabcbcbaabbbbaaccbbaabacaacabcbaaacacbacbabbcbacbbcaabbababcbbcbbbcabaccaacacbcaabacbabacacbbcabaabaaacccbcabccbacbbbacbabaccaccbccbbababbabccccbcbcaaabcbcbbccabbabcabcbbaaccbbbbbccabbbaccbacabbacaacaaccbbaacbbbabcbcababacbcbcbcacbbcccabbcbcbacabacbacabccabbbcbacacbcabcbacaccbacacbaabacbcbccbccbbabbcabccbccabbcbaacacbacbbaaccbbbcaacaccacbabaaacacccaaacbcccabcaabccababcbbbbbbaccbacbbabaaaccacccccbcbbcbbcabbbaccacbaccabbbacabbcbcbccbaabaaaaabcaabbcbabcbabbccbabcbccbcaabcccbacaaabcccabaaccbaaccacaacaccaabbbccacacaacccbbacbcabbbaccbbbbabbbbbababcbacbbbcabcccbacabacabbaabbbbbacbbaabbbccbbcbbcccabbbcbcbbacabcbaacabbabacbacccaccaaabbcbccabccacbababccccbbbaccabbacabbcacabbbbbaaacbabaccccacccabbbbcabbcaaabcbcaabbaccbccccbcaccabaacbcbaaccaabccacbcbcabacbabcabcbaaabbacbabcaaccacccabcaaccaccbccbcbabbbcacaabbbbccccaaabcbcbbcbabacbaaabcaabbbabbbabcbcbacbcbacbccbbccababbbabaaaccbcbbcbacbabbccacbcaaabaccabcbaccacbbbaacbccccbabcbaccacbbcccbaaabccbcabacbacaaaabbbabaabbabbcabbccbabababccbabcabacbaacccacbaccaaacaacacacbabcbacabbcabacacacabbacbcbaccaccbbaaccbabbccccababbbcbbaaabbbbcbccbcabbaabbbcbacaabbabbbaababcacbcccbbbcaabcaacabbaaccabccaaabcabaacaacaccacaabacababbcbbaccabcaccccbcbccbcbcabacacaacaccaabbcabcccbacacbbbbccaaacbaacbabcaaabcbcbacacacccabcccacccacacccbbacbaaaabbcaacaccabcbcbabccbbbcaabbccaaabcaccbccabaabbcbbacbacbcbccabbcbbbacacbbbbcbbbaccaababcbaaaaaabaaaabbbbacaaabcacbacabbaabbabcacaabbccabbbabcabacabcbccaaccccbaacaaacaacbbacccababbacbbbbacbacabbabcccccabcacacbbbacccbaabbcbcacabccccaacaabcbaabacbacabbbbbcccaaabcacaabcacaacaabbabcaacaccbcccacaabcabcabccacabcabbccabcbbcaabbccbccbccbaabcaccbaacabbacabcbabcccbbbcbacbabccbacccbbcbabbacbcbcbcaabababcabacccccacbcbaaaabaaacabacbbbccbcaccacccbcbbbcbcabbababcbccbabaacbabcacbccbababbccabbcbabbbbccbacbbccaaccccbcbbabaacbaccccaacccabacaccccabbabacbbbbbccacbcbccabbbbbaacbccbcccacbcbbcbcabaabbbbbbaabacccbcabccacaccacabbbabcbcacbbbcaaabacbaaaaababaabacababbababbbacbabacbcbabbcbababaacaaabbccbaaaabbbcbcaccacbcbbcbbaccacbbaacbbccccbaaabcabcccccbbcabbaacacccacacabcbbabcaccbbcbcacaccacbbcbcccbcbaabbaacbaacaabcccabcacacbcabbbcaaabccacababcaabacabcbbaabcacbcbbbbabcbabbabaccbbbaacacccbcacccaacbcbbaacbbabbacbccbabbcbbacbbbbbacbbcacbccbaabcaccbcacbaaabcbbaacacccabbcccbabbaacaaaccbbcbbacaacccccbbcbcabbccabaccaabbaccccbbbbbccabcacbabaccbcbbacccccccaabbbbbbbbcaaabbbcbcbcaacaabcbacabbbbcbbbcabbcbccaaccaacbbaaaccbcbcaacbccbacaabbaaaacacbabcccbcaabbbabbcabccaccaccccbbabbccaaacbccccbcbabaacbbaaaaacbaabaaababaacababacccaaacbbaaacabcbacaccabcbcabaababaabbcbabacababbcacbccaaaabaccabacbacbccccaacaabbaaaabcbbaacbaaaaabbcaccaabbbcaccabbbbaacabacccbbcabbcaccccabbacccccccbcbcbccbcbaccbaccbbccbcababcbbbbbcaacabaaabaaaabbcabcabacccaacbccaaccaaaaaabcabaacababbcabaabbbccbccbbababbbaabaabbcaccaacaababcbbccbacabaacbbaabacbaabbacaaaaabbcbccaaaaccbcccaacbaacaacbabaaaacaaabbabbbcabbaabacccbbaacbbaccaccbabccbababcccbccabcabccabcccacbcabaacabbcbababbbaacbbabcaccabbbcccbcbbbaaaccabbaccbbacbbaaabaabaabcababcacaaacbaaabaacbccbbccbabaabcabcccbaacaccbbccacccbcabaacbcbbbacbccbababbccabacbccabacbcabacacabcaacaaccaaabbcaabbaacabacbbbaaababcbacccbaccbbccabacabcacaaccacbacbbaaccaaabbcccaaababbbbacbcabbcbabcccacccaabbccbccaccbbbccaabbbabacbcbccccabaabcabccaccbcbacaabcbbacaaaccabaccacaccacaccabacbaacbcccacbaccabababacbccaaabaaaccaacacabbcabcbbcbabbbbbccaccbcbbaacbabcacabbcacbababcccabaccccbacbcaaaacccaacbbbaaababbabacccbbaabbbbbbbabbcccabcaabccbabcccbabcaaabcaccaccbbcccbaccbbaabcabaabbbbccbbbbcaacaccabccabccbbbaccabcccacaabbbbcbbbaccaacbbacccaabbcccccaaccabcabbccbbabbabcbaababbccaaccaaaabbaccaabbcacccabccacacabacabbcbbccccacbbbbcbbaacabaabccabbbcbbccbbaaabaaabacacbacacaacccabacbcaccaacaacbbbacbbbbccccacccaaabbacbabcbbbcacaacbabbcaacbabbcccaababbabbcaccbaabcacaaacbacaccabbabcbabbbbabaccaaaacaccbcbabbcacaccabcaacababcabacbcccaaacbcacbbababcacacaaabcacccbabbabaaccabcaabcabccbbcabababacbaacaccabcbbbabbbccaacbacccbbccaacbcbbaabacaacaabcbcabccabbccabaaabbabaabaaabbbbccbaccbaabbcaaacacbbcbbcbbbbbccaccabaccbbabbaaccbabbbabcaccccccccaccaacaccbbbaacacbcbaabbcacabbcbbcbaaababbaccacacccbccabcacbcbaabbaccaabcaccbababcbbbaccacccabccaaacbcacabaccacbacaaabbaaccaaabcccabbabbbbbacabbaabccabccbaaabbcbaacacaaaacacaaabcbcbbcbcabbbccbbbaccbcbcabcaccbacbcbbbaacaacaacabbbacababcacabbaacccbccaaacbcaacbacacbbbbaccaacbacbccacccbaaaacaacaaaababbcaaabbccaabbcbaccbbbcbbbcccbababbccaacbaabaaccbcbcbaccbbcbaaaabcacacbccbcbaaaabcbacaccaacacabaabaabcbabaaabbaabbcccacbcbcccacabbaabbabcabccbabbcbbaacabaccbaabcabbbbbccabbcbcabcabaacacccbabcccbbacaacccabcbabccbabccbbaccccbcbbcacbbccaccccbacabcbbcbcbcbccaaccaabaabacbcacbcacbaccacbaaabcbbcaacbccbaaccacbbcaccbcaccbaacbcbacaccbaccbcccacaaabcaccbcbbaccabbaabaaabaaaaabcaabacbabacbcbbabcccbbacbbbbbabaacbbbcbaaacbcbcaccabccababbbbabbbccacaabcababacbcaabacbcbbbbcacacbabcbcaabbcacccacabcbcbabaccbcbaccbcaccbbcbccabbbbabaccabcabaababbaabcabccbccacbacbaacacabbaaccaacabbccabbacbcbabbbaaacbaaaaabaccaacababbcaacababcbccbbacbcabababcabbabbcacacabcabbcacbcaabbcaabaccacabaabacbbabbbababaacbbacbcbcbaacabccacabacbaaaccbaaaaacbacccacbbacbcacabbbcbcbcaabbbccaaccacccbccccbababcacacbbbbcabbbcaacbbacabaacbaaacbbaabcbbaacabcaacbacaaacccabbcccbcaabbcccccbccabcccababbacacaaaacbbcaabccabcabbbbbbcabcbcccaaabccbaabccbcbcbabcbcacccbbcaaccaaaccbaabbbbcccaaccccbccaabbbcacbbabcccaccabaabababbbccbbbcccabbaabacaacacccbcaaabcbaabaaacaacccbbcaacbbaccbabaaaacaaacacabbbcbabaccbbbccacaacacbaabcaaaaaccbabccabacbaaabaccccacccabbbaccaccaabaababbcbbabccbccbaabcacaaabaacaaaacacbbccaaababbcacabbbccbacccaaccaccbabcbaabcbcbcccbcbcbcbbaaaccbaacbaabcccccbcaacbabacbccabbcbcbbacbcbcbcbaaaaacacaabaacbcbabccaababccccbbabcbccaacbbcccbcbcaaacccbccbccacacbcaaacacaacccacbaaabcaaaabacccabccaacaabcbbbaabcbbcabacabacbbbbcabaaaaacacbaacababaabbcbabbbccabbaccbbaabaaabccbcaaacbaccacbcbcbccccbcccbbbcbbaababcabbbbacabcaababaabcbbbcbaaccbabcbacbcccacaabbaabbaabbbcbbaacccbccbbaabbbcbacaabbbaccacbcbcbcbbbcabacabaabaaaabaabccbbacbacbcaabbacbcaabacbbabcbaabbbbbabaccacaacacbcabbcacbbccacccbaabaabaabacbcccbbbcbbbbcaaccaabaaccacabcbcacbaaccbbacacbbbcbaacaccbabcabacabbccbbabcacacaaaacccabacacbbaacabccabbcccaabacbcbcacacbcaabccabacaacbbaaaacbbcbccbacaaccacabcbacaaacaabcaccccbabbaaaccabbaabbabacccbaacacaaccaccbbcbccbccacaacaacbcbcbababaacbccaacbbcabbcbbaccbcbccacaccbaccbaabccbbcbabcacabbcabbcabbbbaaacacccbacbacbbbabcacccacabbabbccccbcccbcaaacccaaaacbabbcbbcaabbccbcabccccacbcbbcccbcabbaabcaaccaabbcbbccbccaaabcbaaabbbbbccaaaaabaabaabbccbcccbbbbbaaababababacacbcabaaccaaabacccccbaaababbbcabcbbaccccbabbbabccbbacbbacbabbbbaccacbcaabbaaccaabcbabbbcaaabcbcaaaaaabacaabcaccbcababbacaababcbaacbbbbcbccacbabcbcbaaaabbacbacbccbaaccabccccbcbccaacbcbbaaacbcacccbbcacbaccacaabaacccccaabcaaaccbcabcbbcaaabacaaaacbccbbcbabbcccaabaacacabaaccbbbaacbbaaabcbabbccacccacabcbbaccccbaabbbaaabcbcaacacacbaccabbbaacabbaabaccacaaabcabacaccbaabaaccccccaabbccacacbaccaaacbabacaaacccaacbbabcabbcccccccabcbacabbbabccbcbacacaaacbcaaababcbcaaccaaaabcbbaacabbacbbbaccbabcccaaccaacabbcbbbaccbbbaaacbcccaaaabaaaabbabccaabbcbcccbacacbccbcbbbcabbbacabaabccccacbaaabbabaacacbbcacacbcacbbbcccbbacbacccbbcccbcbbbccaccbabbbbbcaaccaaabcaccacbabcbbaacbcccbcbcabbcaaccbabababacaccbbcbbbcbcccbbacbcaaaacacbabaaaabbabbbcccbbbcbcbcaabbbbabccbcabbabbabbabccccbbbcaacbccacbcbbccccacaccbbccaaaacbabcacacbbabcacbbbbbbabbccbccabaacbacacbaacbaabaccabbbbacabcbbbcbccbacbbaacccbcabbbcbcccbacbbabcabaabcabaccacabaaacbababbbcaabcccbbaaaaaaaccaacbacabccbaccacabbcbababcbabbbccccabccccbccacbbccccabbbabbcbcacaababbbccbaabbabaaabcabacaacabaaccbcbccacccbbaacacabbcbbbaccbaccbbbbcccabaaababaaacbaacbcbabaccaabbcbcbacaaabbcacabccacbacbacbcbbbccbacbcbbcbababacbbabbcbbbaaaacbbccbaacbaacbaaccaaacabccbbbacaabcabcbacbabbccbccbacaccabccabcbbcabbccbcabccacbbbbcacbabbbbcbacbbaacabccaabbbbbbccaaabcbccaacbaccbaccbacbbbbbabccccbcbbbabccaacbcabaccaaaccbbcabcaaabcbcccaacbcabacaacbacacbabacaaaccaaccabacaacabcabacaacabbababaccacacbaacbccaaccaaabcbaacbcbcacccabaaacbbbbbccbbcbaababaaabaaccbbbabaaacacabccccabbcbcbaabbcacaaacabaabacbacbcaaacaabcabaaacbabbcbaaababcbbaacaabbabbacbcacacbcaaabcbabacbcbaaaacaccabcaaccbcbbcbbbcabbbbacccbbbcaaabbabaaaccbaacabababbacbaaabbbcaacbbcbbbabccaaccbbccbcacabaababcbccbcabbbbcabcacbacbccbccbcbabcbacbccbbcccccabcccbaabbccbccbcbccbacbababcccaccbccbabaabbacccccabccbabcbcbbcbacbccbbccaaaaaabbcacccaabbbbbbbcbaaabbccbacbaaccaaacaabbcbcbaaccbaccbabcabbcccaabbabbccbcaabccaaccbaccbcccabbbbababcbcccaaaabcaccabbcaccaccbccabbcaacbbaabccbbbcacbcaaaaacabcbabccbacacaccaaabaaacabcbcbcbbccbbcbbbbbbcaacbcababbcbacaabcbababccccbccbaaaacabbcacacbcbabccacbcbbaabbaacbbccbaacbacaabbcbbbcacacacccbccacbccacacbaacbabbabbbbaaacbbacbaabbbcbabacacbcbcbaabbcabaaabbcbabbbcccbbabcabcacbbcbcabcbbcbccabcbaccbbbbcacaaaacabbaacacbaccacaaababcacbccccbaaccbaacabccaccacccaabbaaabbcabcbbaaacaaaabcbcccbbaaccbcabaccbacaaacbaccbaccbcbcaabacbaacbaaccaaccaabbaaabbabcbcccaccbaccbcccbcbaaaabacabbabaabcabbcccccacaacbabababcbababbaacabbaaaacabcacccacabaccbaabbaaabcacbaaaacbcbacbacacbbcbbbccaaabbaccbcacababcacbacaaacaccccbbbbaccaccaaccbccbabaabcacbacccabaaabbacaaaacaccacabbababbaacbbabbcabbcacaabbacbaacbaacbaccacaabccbbaacbabcbbaacbacbacbbcababcbaaabcbaababbbaacabcbcbcccabbacabcabcaababbcbaaacbaacaabcabcaabcacaacabaacccbbbabbbcccaccbaabbabaabbcaabccaacaaccccabbacacbbbcacbcabcbbabccabccabbaabbccaaacaccabacbbcccacabbbcabbacaaacacbacccbcbbcbbaacacbbaaabcbbaacacbbcbcccccaabbbbccabaaacbacaabcacacaaacaabaccccabcccbabaaabcacbcaaccbabcaabbbacbcccbbabababaabbcacabcabcbaabbabaabbbcbcccbaacbbacaabbbbbabcabcacbbaabbccbbbababbcbcabbbccababbcbbbabbaaabbbcbbcbaaacacbabccaacbccababaacacbcbbccbcaaccacbccaaaacbbaaabbacacbaababbcbaccbaaacbcccaacabaccbaabaacbbccabaabbbbcbbcbacbcbcbbcacabcbccbcacaccabbacbcababbcababaabbaaccaccccbcbcccaacacbbaccbabaccbbcbbabcaabbcaacaaaaaabccbabacababbacccacccbbabbaccacbabcacacbaccaccabbcbbbcbbbcabccbcccaccacccaabccabcaaaccbacccacacccacaccbbabcacacacbcabccccccaacbcccbaabcaaaabababccbbbcccbbcbcbacccaacaacbccaccccababccbacbbbcbabcbcccabaaccbbcbcaccbababacabccabbabaacbabbbbcaacccbaaaabcaccbbccccbaabbccaabcbaaaaacacbcabaccbacaccabbccbcbbbacbcccccccabbcaccbcaaaaacaaabcabaaabbaaccabbccabbcbcbbabbacabbcbcabcacccccbabbcbbccbccbcccbccaaabbbaacccaabbbcbbaaaacbaccbccbcbacbcabcbbbbabcabacabccaaccabcacbcbbbbacccaabcbbcbabcbcacacbbccbacbacacaabacacbcbcacaaccaccaaccaaacbaaaccaacbabcbbccacaaacbbacccccaccabbcbbbacaaaaaaaccacbcbacabaaaacbcbaaabacbbaabcccaaacccccbccbacabbabbabcbabbccbccabaaccbbbbaaacbaacbbbccbacbaababcbbbccccabbcacbabcbabbbacaabcbbaaccbcabcabccaaaccccbccbcbacbcccccacbacaacccbaabcbabbbabbaacabbababaccbbbbccaaccababaababbabbbabccbbbaaacaacabbccacacbbacbacaccbbaccbcccabcbbccbaacbbbacacbcaccababbaacacccaaccccaaabbccaababcabcbcacbaaabccabcbcbccacbbccaacbcaccbccbbbbcabcbcabcbacbccacaabcabaacccabacbabbcbbbcaabaaaacabaaaacccaabbbacaaccbabcaaaabccacbaababbacbcbccacbbbccabcacaaaabcaaabbbabcbbcacbbbcaaccaacacbaccaabaaabaacacbcacaccbabbbccbccbabcbababcabaaccbaccccacbcabbcbbcabbacabccacbbabcbabcabbcbbbbbacb
bacbcbabcc

正确输出：

276765

我的输出：

276768