QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#816108#1088. Border Similarity UndertakingInvincibleAC ✓787ms102068kbC++232.9kb2024-12-15 22:13:012024-12-15 22:13:01

Judging History

This is the latest submission verdict.

  • [2024-12-15 22:13:01]
  • Judged
  • Verdict: AC
  • Time: 787ms
  • Memory: 102068kb
  • [2024-12-15 22:13:01]
  • Submitted

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <ctime>
#include <random>
#include <cassert>
#include <numeric>
#include <cmath>
#include <bitset>
#include <ext/pb_ds/assoc_container.hpp>
#define pii pair<int, int>
#define fi first
#define se second
#define MP make_pair
#define ep emplace
#define eb emplace_back
//#define int long long
#define rep(i, j, k) for (int i = (j); i <= (k); i++)
#define per(i, j, k) for (int i = (j); i >= (k); i--)
typedef double db;
typedef long double ldb;
typedef long long ll;
//typedef __int128 lll;
typedef unsigned long long ull;
typedef unsigned int ui;
using namespace std;
using namespace __gnu_pbds;
bool Mbe;

//char buf[1<<20],*p1,*p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin), p1 == p2) ? 0 : *p1++)
int read() {
	int s = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9') f ^= (c == '-'), c = getchar();
	while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getchar();
	return f ? s : -s;
}
template<typename T>void chkmax(T&x,const T&y){if(x<y)x=y;}
template<typename T>void chkmin(T&x,const T&y){if(x>y)x=y;}

const int N=2005;
int n,m,D[N][N],U[N][N],L[N][N],R[N][N],f[N][N],g[N][N];
ll ans;
char s[N][N];
void solve(int u,int d,int l,int r){
	if(u==d||l==r)return;
	rep(i,u,d)rep(j,l,r){
		chkmax(U[i][j],u);
		chkmin(D[i][j],d);
		chkmax(L[i][j],l);
		chkmin(R[i][j],r);
	}
	if(d-u<=r-l){
		rep(i,u,d)rep(j,u,d)f[i][j]=g[i][j]=0;
		int mid=(l+r)>>1;
		rep(i,u,d){
			per(j,mid,L[i][mid])f[i][U[i][j]]++,f[i][D[i][j]]++;
			rep(j,mid+1,R[i][mid])g[i][U[i][j]]++,g[i][D[i][j]]++;
			per(j,d-1,i+1)f[i][j]+=f[i][j+1],g[i][j]+=g[i][j+1];
			rep(j,u+1,i-1)f[i][j]+=f[i][j-1],g[i][j]+=g[i][j-1];
		}
		rep(i,u,d)rep(j,i+1,d)if(s[i][mid]==s[j][mid]){
			int valf=L[i][mid]>=L[j][mid]?f[i][j]:f[j][i];
			int valg=R[i][mid]<=R[j][mid]?g[i][j]:g[j][i];
			ans+=valf*valg;
		}
		solve(u,d,l,mid),solve(u,d,mid+1,r);
	}else{
		rep(i,l,r)rep(j,l,r)f[i][j]=g[i][j]=0;
		int mid=(u+d)>>1;
		rep(j,l,r){
			per(i,mid,U[mid][j])f[j][L[i][j]]++,f[j][R[i][j]]++;
			rep(i,mid+1,D[mid][j])g[j][L[i][j]]++,g[j][R[i][j]]++;
			per(i,r-1,j+1)f[j][i]+=f[j][i+1],g[j][i]+=g[j][i+1];
			rep(i,l+1,j-1)f[j][i]+=f[j][i-1],g[j][i]+=g[j][i-1];
		}
		rep(i,l,r)rep(j,i+1,r)if(s[mid][i]==s[mid][j]){
			int valf=U[mid][i]>=U[mid][j]?f[i][j]:f[j][i];
			int valg=D[mid][i]<=D[mid][j]?g[i][j]:g[j][i];
			ans+=valf*valg;
		}
		solve(u,mid,l,r),solve(mid+1,d,l,r);
	}
}

bool Med;
signed main() {
	fprintf(stderr,"%.3lfMb\n",(&Mbe-&Med)/1024./1024.);
	n=read(),m=read();
	rep(i,1,n)scanf("%s",s[i]+1);
	rep(i,1,n)rep(j,1,m)L[i][j]=(s[i][j]==s[i][j-1])?L[i][j-1]:j;
	rep(i,1,n)per(j,m,1)R[i][j]=(s[i][j]==s[i][j+1])?R[i][j+1]:j;
	rep(j,1,m)rep(i,1,n)U[i][j]=(s[i][j]==s[i-1][j])?U[i-1][j]:i;
	rep(j,1,m)per(i,n,1)D[i][j]=(s[i][j]==s[i+1][j])?D[i+1][j]:i;
	solve(1,n,1,m);
	printf("%lld\n",ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 16124kb

input:

3 5
zzzzz
zxzxz
zzzzz

output:

3

result:

ok answer is '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 16188kb

input:

4 4
abbc
bcca
babc
acbb

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 16240kb

input:

12 12
abbabaaaaabb
ababaaaaaabb
aaabbbbbabbb
aabababaaaba
abbbaaabaaba
baaababbbaba
aaaaababbaaa
bbabbbbbabaa
bbbabbaabaaa
aabbbaaaabba
babaabababaa
bababaabaaba

output:

25

result:

ok answer is '25'

Test #4:

score: 0
Accepted
time: 3ms
memory: 24760kb

input:

200 200
aabababbaabbaabaaaabbabaaaaabababbbaaabbbbbbaabbbbbababaabbbabaaaabaaababababababbbbbbabababbbbbababbaababbabaabababbbaabbaaaabbababbaabbaaaaaababbbbbbbbabababbbbababbaaaabbabaaaabaaaababaababaabaabaa
bbabababaabbaaabaaaaabbabbbbbbaabaababaaaabaaaaabbbbbababbaaabbaaabbbaaaabaabbbabbabbaababa...

output:

9063

result:

ok answer is '9063'

Test #5:

score: 0
Accepted
time: 5ms
memory: 24772kb

input:

200 200
bbcacaacbcabaacacbacabcccbbacbbbabaccbcabacbacaccbabcbcbaaacbacbaccbbacabbabbbbaccabcacbccaaaaaabacbcabcacbcacbbcbcbbababcccabccaaacabcbccbcbacccbbbcacacbcbbaccaabcbcababbccbcbacbcaaaacabaccaabacabbca
abbbbaacabcbabacaabcccbbcabaabcaacacacacbabbccbabbcbbcbacbbaababbcbbcacbbbabcbbcbbbbabaaaab...

output:

1993

result:

ok answer is '1993'

Test #6:

score: 0
Accepted
time: 3ms
memory: 24780kb

input:

200 200
daadbcdabdabbcbabacdbdaaabbbdbcbbcdaacababcbbdcdbadbadbbccdcbdbbabbddadaccaaaddacdaddaadaaacbdacbcacbdbcaaddddadcdacaaaaccdaadadaaabadbbdcbcbadccbcabccddaddbcdadbdcddcdbaabaacccdaddcdddcaccbddcdaddcbc
adadabcbbacacdadbbaadbbacaccccaabcadbccdddcdbaabacdcaaccbddaadcbcaadcccdbcdccdacbbbbcbabdcb...

output:

725

result:

ok answer is '725'

Test #7:

score: 0
Accepted
time: 3ms
memory: 24776kb

input:

200 200
txxwjvdrstzdlvxbapbangqherrnvedtncukdffoafsxdpbjhowrytghnpxjdylejgnxmvagxqkgrmektefspdsfzyshkavoputrpszynegndfaxqwuexqhsoqqixyakpshebggckjonwsjaiffhgpimqblmjymlltdanrmkgfpvmuzdntucrrtverpfdeellblawwyk
jieyodnvjkcmuomidegwcrinowmvivwnqvwwffmmhxjktznptunvuxcxanknhevtgchvotjifeutehgbsemomcvtahx...

output:

4

result:

ok answer is '4'

Test #8:

score: 0
Accepted
time: 0ms
memory: 26460kb

input:

200 20
bbabbbaabbababbbbbbb
bbbabbbbbababbbabaab
bbabbbabbbbbbbbbbbab
abaaabbbbbabbbaaabba
ababbbbbbbbabbbabbbb
baababbbababbbbbbbab
baabbabbbaaaabbababb
bbbbbabaabbbbabbbbaa
bababbbbbbbbbbbbbbab
bbbaabbbbaabbabbabba
bbabbbbbbbbbaabaabbb
bbbbbbbabbabaabbbabb
bbbbbaabbbaabbbbbaba
aabbaabbababbabbbbab...

output:

5669

result:

ok answer is '5669'

Test #9:

score: 0
Accepted
time: 0ms
memory: 24720kb

input:

200 20
bbbbbbabbbbabbbbbbba
bbbbabbbbabbbbbabbbb
bababbbbbbbbbbabbbbb
bbbbbbbbabbbbbabbbba
babbbbbabbbbbbbbbbbb
bbbbbbabababbbbbbbbb
bbbbbbbbabbbbbbbbbbb
bbbbbbbbbbbbbbabbbbb
bbbbbbbbbbbbbbaabbbb
bbbababbbbbbbbbbbbbb
bbbbbbbbbbbabbbbbaba
abbbbbbbbbbbbbbbbbba
bbbbbbabbabbbbbbbbbb
bbbbabbbbbbbbabbbbbb...

output:

30317

result:

ok answer is '30317'

Test #10:

score: 0
Accepted
time: 0ms
memory: 24820kb

input:

200 20
bbbbabbbbbbbbbbbbbab
bbbbbbbbbbbbbbbbbbba
bbbabbbbbbbbbbabbbbb
bbbbbabbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbabaabbbbbb
abbbbbbbbbbbbbbbaabb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbabbbbbbbb
abbbbbbbbbbabbbbbbab
babbbbbbbbbbabbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbaaabbbbbb
abbbabbbbbbbbabbbbbb...

output:

138080

result:

ok answer is '138080'

Test #11:

score: 0
Accepted
time: 0ms
memory: 24760kb

input:

200 20
babbbbbbbbbbbbbbbabb
babbbbbbbbbbbbbbbbbb
bbbbbbabbbbbbabbbbbb
bbbbbbbbbabbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbabbbbbbbbbbbbb
bbbbaabbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbabb
bbbababbbbbbbbbbbbbb
bbbbbbbbbbbbabbbbbba
bbbbbbbbbbbbbbbbabbb...

output:

371054

result:

ok answer is '371054'

Test #12:

score: 0
Accepted
time: 0ms
memory: 24764kb

input:

200 20
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
babbbbbbbbbbbbbbbabb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbabbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbabbbbb
bbbbbbbbbbbbbabbbbbb
bbbbbbbbbbbbbbbbbbbb...

output:

636400

result:

ok answer is '636400'

Test #13:

score: 0
Accepted
time: 2ms
memory: 24820kb

input:

200 20
bbaabaaaababaaaaaaaa
baabaabaaababbaaaaba
ababaaaaababaaaaabaa
baaababaaaabaaaababa
aaaaabaaaaabbaabaaab
aabaaaabaababbabaabb
aaaaaaaaaaaaaaaaaaaa
aabaaaaabaabbbabaaaa
aaaaaaabbaaabaaabbaa
aaabaaaaaaaaaaaaaaaa
aaaabaaabaaaaabbaaba
bbabbabbbaaaabaaaaab
aaaaaaabaaaababaaaba
aaaaabbbabaaaaaaaaab...

output:

5557

result:

ok answer is '5557'

Test #14:

score: 0
Accepted
time: 0ms
memory: 24796kb

input:

200 20
abaaaaabaaaaaaaaabaa
aabaaaabbaabaaaaaabb
aabaabaaabaaaabaaaaa
aaaaabaaaaaaaaaaaaaa
aabaabababbbaaabaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaabaaaaaaaaaa
aaabaaaaaaaaaaaaaaaa
bbababaaababaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aabaaaabbaaaaaaaaaaa
abaaaaaabbaaaaaaaaaa
aaaaabaaaaaaaaaaaaaa
baaaabaabaaaaaaaaaaa...

output:

26980

result:

ok answer is '26980'

Test #15:

score: 0
Accepted
time: 0ms
memory: 26840kb

input:

200 20
aaaaaaaaaaaaaaaabaaa
aaaaaaaaaaaaaaabbaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaabbaaaabaaaaaa
aaaaaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaaaaaa
aaaaaaaabaabbaaaaaaa
aaaaaaaaaaaaaaaabaaa
aaaaaaaabaaaaaaaaaaa
aaaaaaabaaabaaaaaaaa
aaaaaaaaaaaaaaaabaaa
aaaaaaaaaaaaaaabaaaa
aaaababaaaaaaaaaaaaa
baaaabaaaaaabaaaaaab...

output:

128439

result:

ok answer is '128439'

Test #16:

score: 0
Accepted
time: 0ms
memory: 24700kb

input:

200 20
aaaaaaaaaaaaaaaaaaaa
aaaaaabaaaaaaaaaaaaa
aaaaaabaabaaabaaaaaa
aaaaaaaaabaaaaaaaaaa
aaaaaaaaaaaaaaaaabaa
aaaaabaaaaaaaaaaabba
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaabaaaaaaaaaaaaba
aaaaaaaaabaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaabaaaaaaaaaaaaa
aaaaaababaaaaaaaaaaa...

output:

431605

result:

ok answer is '431605'

Test #17:

score: 0
Accepted
time: 0ms
memory: 24820kb

input:

200 20
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaba
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaabaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa...

output:

721991

result:

ok answer is '721991'

Test #18:

score: 0
Accepted
time: 7ms
memory: 24756kb

input:

200 200
bbbbbbbbaabbaabbbbabbbbbbbbbabbbababbbbbbbbbbbbbbbbabbbabbbbbbabbbbabaaabbbbbbbbbbbbaabbaababbabbbabbbbbbababaabbbbbabbbaabaabbbbbabbabbababbbbbbbaabaababbbababbbbbababbababbbbbbbaababababbbbbabbabbbb
bbbbbbbbbbbbbabbbbbbabaabbaabababbaaaaaabbbbbabbbbabbbbabbbbbabbbbbbababbbbbbbbaabbbbabaaba...

output:

65918

result:

ok answer is '65918'

Test #19:

score: 0
Accepted
time: 5ms
memory: 24772kb

input:

200 200
bbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbabbbbbbbbbabbbbbbabbbbbbbabbbbbbbbbbbbbabbbabbbbbbbbbabbbbbbbabbbabbbbbbbbbbabbbabbbbbbbbbbbbbbaababbbbbbbbbbabbbbaabbbbabbbbbbbbbbbabbbbbbbbbbabbbabbbbabbbbbb
bbbbabbbbbbbbbbbbbbabbbbababbbabbbbbabbbbbbbbbababbabbbbbbbbbbbbababbbbbbbbabbbaaababbbbbbb...

output:

436980

result:

ok answer is '436980'

Test #20:

score: 0
Accepted
time: 5ms
memory: 26364kb

input:

200 200
bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbbbabbbbbbbabbbbab
bbbbbbbbbbabbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbabbbabbab...

output:

2006888

result:

ok answer is '2006888'

Test #21:

score: 0
Accepted
time: 3ms
memory: 26576kb

input:

200 200
bbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbbbbbbbb...

output:

8811371

result:

ok answer is '8811371'

Test #22:

score: 0
Accepted
time: 5ms
memory: 26748kb

input:

200 200
bbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbabbbbbbbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbb...

output:

29949725

result:

ok answer is '29949725'

Test #23:

score: 0
Accepted
time: 5ms
memory: 26608kb

input:

200 200
aabaaaaaaaabaaaaaabaaaaabaaabaaaababaabaabbaabaaaaaaaaaabaaaaaaabaaaaaababaaabbabaaababaababaaaaaaaaaaaabaaaaabaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaababbaaaaaaaaaaaaaaabaaabaabbbbabaaaaaaaaaaaaabaaa
aaaaaaaabbaaaaaaaabbaaaaaabaabbaaaabaaaabbabaaaabaaaaaabaaaaabbbaaaabaaabaaabbababbabbaabaa...

output:

62746

result:

ok answer is '62746'

Test #24:

score: 0
Accepted
time: 5ms
memory: 26876kb

input:

200 200
aabaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaaaaaaaababaabaabaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaabaaabaaaaaaaabaaaaaabaaaaaaaaaaaaaaabaabaaaabaaaaaaaaabaaabaaaaaaaaaaaabaaaaaabbaaaabaaaa
aabaaaaabaabaaaaaaababaaabaaaaaaabaaaaaaaaaaaaaaaaabbabaaaaaaaaaaaaaaaaaaaaaaababaabbaabaab...

output:

393455

result:

ok answer is '393455'

Test #25:

score: 0
Accepted
time: 6ms
memory: 26628kb

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaababaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaa...

output:

1744602

result:

ok answer is '1744602'

Test #26:

score: 0
Accepted
time: 4ms
memory: 24716kb

input:

200 200
aaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaa...

output:

7733272

result:

ok answer is '7733272'

Test #27:

score: 0
Accepted
time: 3ms
memory: 24768kb

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaa...

output:

26388726

result:

ok answer is '26388726'

Test #28:

score: 0
Accepted
time: 411ms
memory: 101980kb

input:

2000 2000
hxbcuprmlgnupldnbzhcpesdlawilpqilczdvavjoetwdjtjkcdccftawgagfjhfcnkejypkgwswgiibgfxzzcgjdqjmamdkttedmffqievedyicgurwmungupmvuwralxutfnrykylbqrbqquvrchuuoebfapvgsjgasdfnkxrjnflizeqychfhuetijdnuoenucqkktzkurqcpusbncvilxziylxxyprsqwcdrgcviobiapvuxvhignilpavhjuebiwhatxtqvemtmxwlufvdkmqstjpqvos...

output:

238

result:

ok answer is '238'

Test #29:

score: 0
Accepted
time: 713ms
memory: 101948kb

input:

2000 2000
aabbbabababbbbbbbaabbaabbbbabbaabbbbbbbbabbaabbabaababababbbbbbabaaabbbbbabbaabbaabbaaaabaaabaaaaaabbbbaaaaabbbbabbaaaababbaaaabbaabaababaaaabaaaaaabbbaabaabbbbbabaaaaaaabaaabbaabaababaaabbbaababababaabbbbbaabbbaabaaabbbbaababaaabaaabbaabaaaaaababbabbaaabbbababaabaabaabbbaabaabbbbbaaababbb...

output:

888377

result:

ok answer is '888377'

Test #30:

score: 0
Accepted
time: 30ms
memory: 49128kb

input:

100 2000
baaabbabbaaababaaababbbabbabaaaabbbbbbbbabababbaabaabaaaaaaaabbbbbaaaaaaaaaabaabbbaabaabaaabaaaababbbbbaaaaabbbaaabbbaababbaaaaabbabaaaaaaaabaabaabbbbbbbbbaaabaababbaaabbbaabbaaaaaaabbbabaaabbabbbaaaabbabbababbaaaabbabbaaaaaababbbbababaabbabbabbbbbabbaababbabbbaabbbaabbababbbabbabbaaabbbbbb...

output:

44364

result:

ok answer is '44364'

Test #31:

score: 0
Accepted
time: 0ms
memory: 37732kb

input:

3 2000
abaabbbbaaabbbaaaababaaaabbbbaaaaabaabbaaaabbaaaaabababaababababbbabbbabbbabbbbbabaaabaabaabbaaabaaabbabbaabbabbbbabaabbabbbaabbbbbabbabbbababaaaabaabaabaaaabaabaabaaaaabbababbbbbaabbabbaababbbaaababaaaaaaababbbabbaabbabbbababaababababbabbbababbbaabbabaaaabbaabaaaabbaabbabaabaababbababbbabaab...

output:

771

result:

ok answer is '771'

Test #32:

score: 0
Accepted
time: 0ms
memory: 16192kb

input:

2 2000
aabaabaaabbbbaababbaaabbabaaaaabaaabbbabababaaaaabaabbaababaaabbaaaabaabaababbabbbbaaabbbbbaabaaaabbaababbaabaaabbbbbbaaaaabababbaaaababbbabbbbaabbbbaabaaaaaaaaaaabbbabaaaaaabababaaaaabbaaababaabababababaabbbabaababbbabbaaaaabbabbaaaaaabbbbaabaaabbaabaaabbbbbaabaaabaaaaaabbaababbaaaaabbabbbba...

output:

309

result:

ok answer is '309'

Test #33:

score: 0
Accepted
time: 787ms
memory: 101892kb

input:

2000 2000
bbbbbbbbbababbbbbbbbbbabbabbbbbbbabbbbbbbbbababaaabbaabbbbaabbaababbbaabaabbabbbbbaaababbbabbabbbbbbabbbbbababbabbabababaabbbbabbbbabbabbbabbbabbbbabbbbabbabaaabbbbaabaababbbbbbaabaabbbbabbbbaaabbbbbaabbabbaabababaabbbbbbbbbbababaababbbbbbbbbbababaabbbaabbbbbbbbbbbbbabbbaaabaabbbbbabbbabbb...

output:

6611891

result:

ok answer is '6611891'

Test #34:

score: 0
Accepted
time: 734ms
memory: 101900kb

input:

2000 2000
bbabbbbbabbbbbbbababbabbbbbbbbabbbbbbabbabbbababbbbbbbbbbbbbabbbbbbbbbbbbabbbababbbbbbbbbbbbbbbbbbbabbbbabbbbabbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbabbbbbbabbbbbbbbbbabaababaabbbbbbbbbbbbbbbbbbabbbbabbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbabbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

42485356

result:

ok answer is '42485356'

Test #35:

score: 0
Accepted
time: 677ms
memory: 101932kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbabbbbbabbbbbbaabbabbbbbabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbb...

output:

208474291

result:

ok answer is '208474291'

Test #36:

score: 0
Accepted
time: 658ms
memory: 101984kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbababbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

920144952

result:

ok answer is '920144952'

Test #37:

score: 0
Accepted
time: 649ms
memory: 101940kb

input:

2000 2000
bbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3800182739

result:

ok answer is '3800182739'

Test #38:

score: 0
Accepted
time: 741ms
memory: 101972kb

input:

2000 2000
aaaabbabbabaaaaabaaaaabbaaaabaabaabaaaaaaaaaaaabaababaaabbaabaababaaaaaaabaabaaabbbabaaaaabaaaabaaaaaaaaaaaaabaaaaaaaabbaaaabaaaaaaaaaabbbaabaabaaaaaabaaaaabbaaaaababaaaaaabbaaaaaaabaaaaaabaaaaabbbaaaaaaaaabbbababaaaaaaaaaabaaaaaaaaaaaaaababababaaaaaaaabbaaabaaabbaabbaaaaababaaaaaabaaaabaa...

output:

6633997

result:

ok answer is '6633997'

Test #39:

score: 0
Accepted
time: 720ms
memory: 101932kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaabaaaabaaaaababbaaaabaaaababaaaaaaabaaaaaaaaaaaaaabaaabaaaaaabaaaaaaaaaaaabbaaabaaaaababaababaaaaabababaaaaabaaaaaaaaaaabaabbaaaabaaaaaaaabaaaaaaaaaaaaaaaabbaaaaaaaabaaaaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaabaaaaaaabaaaaaaaaaabaaaaaaaaabbabaaaaababaabaabaaaaaaaa...

output:

42677036

result:

ok answer is '42677036'

Test #40:

score: 0
Accepted
time: 680ms
memory: 101888kb

input:

2000 2000
aaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaabaaabaaaaabaaaaaaaaaaaaaabaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaabaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaa...

output:

209624629

result:

ok answer is '209624629'

Test #41:

score: 0
Accepted
time: 660ms
memory: 101944kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaba...

output:

908496629

result:

ok answer is '908496629'

Test #42:

score: 0
Accepted
time: 623ms
memory: 101928kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3819264516

result:

ok answer is '3819264516'

Test #43:

score: 0
Accepted
time: 572ms
memory: 101928kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2193746696652

result:

ok answer is '2193746696652'

Test #44:

score: 0
Accepted
time: 569ms
memory: 101964kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2886592675758

result:

ok answer is '2886592675758'

Test #45:

score: 0
Accepted
time: 541ms
memory: 102020kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3460768674956

result:

ok answer is '3460768674956'

Test #46:

score: 0
Accepted
time: 547ms
memory: 102068kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3680478183757

result:

ok answer is '3680478183757'

Test #47:

score: 0
Accepted
time: 551ms
memory: 102012kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3834982314152

result:

ok answer is '3834982314152'

Test #48:

score: 0
Accepted
time: 552ms
memory: 102016kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2113716926482

result:

ok answer is '2113716926482'

Test #49:

score: 0
Accepted
time: 537ms
memory: 102012kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2884992951736

result:

ok answer is '2884992951736'

Test #50:

score: 0
Accepted
time: 558ms
memory: 102012kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3434267490537

result:

ok answer is '3434267490537'

Test #51:

score: 0
Accepted
time: 554ms
memory: 102016kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3693371002932

result:

ok answer is '3693371002932'

Test #52:

score: 0
Accepted
time: 527ms
memory: 102064kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3833465918348

result:

ok answer is '3833465918348'

Test #53:

score: 0
Accepted
time: 540ms
memory: 102024kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #54:

score: 0
Accepted
time: 532ms
memory: 102040kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #55:

score: 0
Accepted
time: 0ms
memory: 42868kb

input:

20 2000
bbbbbabbbabbbbbabbbbbbbbaaaabaabbaabbbbaabbbabbabbabbaabbbabbabbabbbbbbaabbbbbababbabbbbbbabbbbbbbbbbbaabbabbbbbaababbbbbbbbabbbabbbbbbbabbbbbbbbbabbbabbabbbbaababbbbbbbbaabbbabbbbbbbbbabbbaabbbaabbbbbababbbbbbbbabbbbbbbabbbbbbbbabbbbbababbbbbbbbbbbbbbbbababbbbbbbbbbbaaabbabbbbabbbbbaabbbbab...

output:

56816

result:

ok answer is '56816'

Test #56:

score: 0
Accepted
time: 13ms
memory: 42844kb

input:

20 2000
bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbababbabbabbabbbbabbbbbbabbbabbbbbabbbbabbbbbabbbbbbabbbbbbbbbbbbaabbabbbbababbbabbbbbbbbbbabbbabbbbbbbbbbbbbbbaabbabbbbbbbbbbbbbbabbbbabbabbbbbbbabbabbbbbbbbbbbabbbbabbbaabbaaabbbbbbbabbbbbbbbbbbbbabbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbabbbb...

output:

355419

result:

ok answer is '355419'

Test #57:

score: 0
Accepted
time: 4ms
memory: 44896kb

input:

20 2000
abbbbbabbbabbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbaabbbbbb...

output:

1290507

result:

ok answer is '1290507'

Test #58:

score: 0
Accepted
time: 0ms
memory: 44964kb

input:

20 2000
abbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbb...

output:

3673870

result:

ok answer is '3673870'

Test #59:

score: 0
Accepted
time: 8ms
memory: 42860kb

input:

20 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

9771068

result:

ok answer is '9771068'

Test #60:

score: 0
Accepted
time: 10ms
memory: 42892kb

input:

20 2000
babaabaaaababaaabaaaaaaaaaaaabaaaabaaaaaabbaababaababaaaaaaaaaaaaaabaaaaaaaabaaaaaabbaaaaaaababaaaaaaabaaabaaaababaaaabaaaabbbababaaaaaababaaababaaaaaaaabaaaaaaabaaababaaabaaaaaaababaabaaaaaabaaaaaaaaaaaabaaaaaaaaabaabbaaaababaaaaaabaaaababaaaaabaabbabaaabbaaaabaaaaababababaabaabaaaaabaabaaa...

output:

57804

result:

ok answer is '57804'

Test #61:

score: 0
Accepted
time: 0ms
memory: 46956kb

input:

20 2000
aaaaaaaaaaabaaabaaabaaaaabbbaaaaaaaabaaaaaaaabaabaaaaaabaaaaabababbaaaaaabaaaaaaabbabaaaaaaaaaaaaaabaaaaaaababaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaababaaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaabaaaaaaabaaabaaabaaabaabaaabaaaaaaabbaaaaabaabaaaabaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaa...

output:

361169

result:

ok answer is '361169'

Test #62:

score: 0
Accepted
time: 4ms
memory: 44920kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaababaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaa...

output:

1287432

result:

ok answer is '1287432'

Test #63:

score: 0
Accepted
time: 9ms
memory: 46964kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba...

output:

3785925

result:

ok answer is '3785925'

Test #64:

score: 0
Accepted
time: 0ms
memory: 46920kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

9744215

result:

ok answer is '9744215'

Test #65:

score: 0
Accepted
time: 3ms
memory: 100932kb

input:

2000 20
bbbbabbbaababbbbbbbb
bbbbaabbabbbabbbbaba
babbabbbbbbbabbbbabb
ababbbbbbababbbbabbb
baaaabababbbbbbbbbba
bbbabbabbabbbbbbbbba
bbbabbbabbabbbbababb
bbbbbbabababbbbabbbb
babbbbbabbbbbbbaabbb
abbbbbbbbbbabbbbabbb
bbbbbbbbbabbbbbbabbb
abbbbbbbaabbbbbbbbbb
abbabbbabbbbbabbbbaa
bbbbbabbbbabaabbbba...

output:

56385

result:

ok answer is '56385'

Test #66:

score: 0
Accepted
time: 8ms
memory: 101392kb

input:

2000 20
bbbbbbbabbbbbbbbbbbb
bbbbbbbbbbbbbabbbbab
bbbbbbabbbbbbbbbbbab
bbbbabbabbbaabbabbab
abbbbbbbbbababbbbaab
bbbbbbabaababbabbbbb
bbbbabbbaabbbbbbbabb
bbbabbbbbabbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbabb
bbbbbbbbabbbbbbbbbbb
bbbbbbbbabbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbabbbbbb...

output:

348282

result:

ok answer is '348282'

Test #67:

score: 0
Accepted
time: 8ms
memory: 101532kb

input:

2000 20
bbbbbbbbbbbbbbbbbbbb
bbabbbbbabbbbbbbbbbb
babbbabbbabbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbaabbbbbbbbab
abbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbabbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbabbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbabbbbb
bbbbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbab...

output:

1198544

result:

ok answer is '1198544'

Test #68:

score: 0
Accepted
time: 3ms
memory: 101688kb

input:

2000 20
bbbbbbbbbbbbbbbbbbbb
bbabbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbabbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbabbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbabbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbabbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbabbbb...

output:

3642961

result:

ok answer is '3642961'

Test #69:

score: 0
Accepted
time: 0ms
memory: 101188kb

input:

2000 20
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbabbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbabbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
abbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbb...

output:

9234628

result:

ok answer is '9234628'

Test #70:

score: 0
Accepted
time: 4ms
memory: 102000kb

input:

2000 20
aabaaabbbaaaaaababaa
aaabaaaaaaaaaabaaaab
babbaaaabaaabaabaaaa
baaababbabaaaababaaa
abbaaaabaaaaabaaaaaa
aaaaaaaaabaaaaabbaaa
aaaabaaababaabaaabaa
aaaaaababbabaaaaaaab
baaaaaaaaaaaaaabaaab
aaabbaaaaaaaaababaaa
aabaaaaaaaabababaaba
bbaaaaaaabaaababbbba
aaaabaaaaabaabaaabab
babaabaabaaaaaaaaaa...

output:

57704

result:

ok answer is '57704'

Test #71:

score: 0
Accepted
time: 7ms
memory: 101336kb

input:

2000 20
babaaaaaabaaaaaaaaaa
aaaaaaaaaaaaabaaaaaa
aaaaaabaaaaaaaaaabaa
aabaaabaaaaaaaaaabaa
aaaaaaaaaaabaaaaaaaa
abaabaaaaabaaaaaaaaa
bbbaaaaaaaabaaaaaaaa
aabbaaaaaaaabaaaaaab
baaaaabaaaaaaaaaaaaa
aaaaaaabaaaabaaaaaaa
baaaaaaabaaaaaaaaaaa
abaaaaaaaaaaaaaaabaa
aaaaaaaaaaaaabaaaaaa
aaaaaaaaabaaaaaaaba...

output:

346719

result:

ok answer is '346719'

Test #72:

score: 0
Accepted
time: 0ms
memory: 101528kb

input:

2000 20
aaaaabaaaaaaaaabaaaa
aaaaaaaaaaabaaaaaaaa
aaaaaaaaaaaaaaaaabaa
aaaabaaaaaaaaaaaaaaa
aaaaaabaaaaabaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaabaaaaaaa
aabaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
ababaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaabaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaab
aaaaaaaaaaaaaaaaaaa...

output:

1248199

result:

ok answer is '1248199'

Test #73:

score: 0
Accepted
time: 8ms
memory: 101796kb

input:

2000 20
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaababaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaabaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaabaaaaaaaaaaaaaaa
aaaaaaaaaaababaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaabaaaaa
aaaaaaabaaaaaaaaaaa...

output:

3835772

result:

ok answer is '3835772'

Test #74:

score: 0
Accepted
time: 0ms
memory: 101488kb

input:

2000 20
aaaaaaaaaaabaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaabaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaabaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaa...

output:

9533317

result:

ok answer is '9533317'

Test #75:

score: 0
Accepted
time: 471ms
memory: 102064kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaa...

output:

2191400000

result:

ok answer is '2191400000'

Test #76:

score: 0
Accepted
time: 442ms
memory: 102068kb

input:

2000 2000
ccccccccccccccccccccaaaaaaaaaaaaaaaaaaaavvvvvvvvvvvvvvvvvvvvppppppppppppppppppppvvvvvvvvvvvvvvvvvvvvttttttttttttttttttttvvvvvvvvvvvvvvvvvvvvoooooooooooooooooooorrrrrrrrrrrrrrrrrrrrnnnnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaajjjjjjjjjjjjjjjjjjjjrrrrrrrrrrrrrrrrrrrrwwwwwwwwwwwwwwwwwwwwiiiiiiiiii...

output:

416024000

result:

ok answer is '416024000'

Test #77:

score: 0
Accepted
time: 500ms
memory: 102016kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

151925000000

result:

ok answer is '151925000000'

Test #78:

score: 0
Accepted
time: 466ms
memory: 102024kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

45969000000

result:

ok answer is '45969000000'

Test #79:

score: 0
Accepted
time: 475ms
memory: 102024kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

536440500

result:

ok answer is '536440500'

Test #80:

score: 0
Accepted
time: 438ms
memory: 102004kb

input:

2000 2000
ddddddddddkkkkkkkkkkrrrrrrrrrrwwwwwwwwwwvvvvvvvvvvaaaaaaaaaaoooooooooottttttttttttttttttttzzzzzzzzzzqqqqqqqqqqssssssssssuuuuuuuuuuuuuuuuuuuuxxxxxxxxxxnnnnnnnnnnuuuuuuuuuuzzzzzzzzzzeeeeeeeeeeuuuuuuuuuubbbbbbbbbbnnnnnnnnnnmmmmmmmmmmccccccccccppppppppppnnnnnnnnnnhhhhhhhhhhllllllllllgggggggggg...

output:

95748500

result:

ok answer is '95748500'

Test #81:

score: 0
Accepted
time: 490ms
memory: 102064kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

49867000000

result:

ok answer is '49867000000'

Test #82:

score: 0
Accepted
time: 462ms
memory: 102028kb

input:

2000 2000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

10989000000

result:

ok answer is '10989000000'

Test #83:

score: 0
Accepted
time: 527ms
memory: 102016kb

input:

2000 2000
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

998001000000

result:

ok answer is '998001000000'

Test #84:

score: 0
Accepted
time: 507ms
memory: 101988kb

input:

2000 2000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

249001000000

result:

ok answer is '249001000000'

Test #85:

score: 0
Accepted
time: 0ms
memory: 12084kb

input:

1 1
b

output:

0

result:

ok answer is '0'

Test #86:

score: 0
Accepted
time: 3ms
memory: 72848kb

input:

2000 1
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b...

output:

0

result:

ok answer is '0'

Test #87:

score: 0
Accepted
time: 0ms
memory: 73024kb

input:

2000 1
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a...

output:

0

result:

ok answer is '0'

Test #88:

score: 0
Accepted
time: 0ms
memory: 71312kb

input:

2000 1
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a
b
b
b
b
b
b
b
b
b
b
a
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
b
a
b
b
b
b
b...

output:

0

result:

ok answer is '0'

Test #89:

score: 0
Accepted
time: 0ms
memory: 72776kb

input:

2000 1
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
b
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a...

output:

0

result:

ok answer is '0'

Test #90:

score: 0
Accepted
time: 2ms
memory: 12092kb

input:

1 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #91:

score: 0
Accepted
time: 0ms
memory: 12104kb

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #92:

score: 0
Accepted
time: 2ms
memory: 12092kb

input:

1 2000
bbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #93:

score: 0
Accepted
time: 0ms
memory: 12084kb

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #94:

score: 0
Accepted
time: 2ms
memory: 12136kb

input:

1 2000
bbaaabbbabbbbabbbbbbbaaaabbabbbababbbbabaaaaababbabbbbbaabbbaababbabbbaaabaaabaabbabbababbbabbbbbbaabbbbbaaabbbaabababaaaaabbbaabbbaabbbaaaabbbbaaaababbbababaabaabbaabbabaaabaaaaababaaaabaaabababbbbbaababbaabaababbaababababbabaaababbaaabbbbabbbbbabbabbbaabbbaaaaaaaaaaabbabbbaaababbaababababba...

output:

0

result:

ok answer is '0'

Test #95:

score: 0
Accepted
time: 0ms
memory: 12096kb

input:

1 2000
ybznxtzkzdspabhllysnjejgxhynartagoluiafvuzylklphybjbgbydzwviwrjqqcocnryvxzhilkcbzljokipgrdvilnghahtznvxlfofzrhzqwotlfgeyaratruepvpnfianhskanisdjwmekyahnaaeagdxtplxxudezjkusekalweqvvkaghkhbewxufzucflhkkwjcfikolebosrreyfdoxwgjlqvtvmmbykpzlelzoufjtskvkhilfuesudaugjalzhsjmnxhauphiglkrfpigxueotfds...

output:

0

result:

ok answer is '0'

Test #96:

score: 0
Accepted
time: 0ms
memory: 72720kb

input:

2000 1
a
b
a
b
b
a
a
b
b
a
b
b
a
b
b
b
b
b
b
b
b
b
a
b
a
a
b
b
b
a
a
b
a
a
a
a
b
b
a
b
b
b
a
a
a
b
a
b
b
b
b
a
a
b
b
b
b
b
b
b
b
a
b
b
b
a
a
a
b
a
b
a
b
a
a
b
a
a
b
b
b
b
b
a
a
a
a
b
a
a
b
b
a
b
a
b
b
a
b
a
b
a
b
a
b
b
b
b
b
b
a
b
a
b
a
a
b
a
b
b
a
b
a
b
a
b
a
b
a
a
a
a
a
b
a
b
b
b
b
a
a
a
a
a
b
b
b...

output:

0

result:

ok answer is '0'

Test #97:

score: 0
Accepted
time: 0ms
memory: 73168kb

input:

2000 1
v
o
j
f
d
l
i
c
u
z
s
u
a
r
w
a
i
a
m
o
m
r
a
e
h
j
l
x
s
v
b
v
p
a
l
s
h
x
r
j
w
w
k
u
i
x
f
m
b
v
j
w
u
u
s
g
n
v
e
t
u
u
y
h
n
x
y
k
k
l
d
g
g
q
z
h
t
m
v
p
w
e
k
t
p
p
o
f
q
d
d
g
f
h
u
m
l
z
n
w
r
n
a
g
h
h
s
i
k
k
u
l
f
i
d
p
r
d
b
t
d
x
y
d
n
l
t
p
g
r
g
e
h
p
e
c
b
f
j
i
h
y
p
u
t
r
w...

output:

0

result:

ok answer is '0'