QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19727#1088. Border Similarity UndertakingwlzhouzhuanAC ✓3367ms132840kbC++173.8kb2022-02-09 14:56:552022-05-06 06:52:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 06:52:22]
  • 评测
  • 测评结果:AC
  • 用时:3367ms
  • 内存:132840kb
  • [2022-02-09 14:56:55]
  • 提交

answer

// Author: wlzhouzhuan
#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define per(i,l,r) for(int i=(l);i>=(r);i--)
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define mset(s,t) memset(s,t,sizeof(s))
#define mcpy(s,t) memcpy(s,t,sizeof(t))
#define SZ(x) ((int)x.size())
#define pb push_back
#define eb emplace_back
#define fir first
#define sec second

template<class T1,class T2>bool ckmax(T1 &a,T2 b){if(a<b)return a=b,1;else return 0;}
template<class T1,class T2>bool ckmin(T1 &a,T2 b){if(a>b)return a=b,1;else return 0;}

inline int read(){
    int x=0,f=0;char ch=getchar();
    while(!isdigit(ch))f|=ch=='-',ch=getchar();
    while(isdigit(ch))x=10*x+ch-'0',ch=getchar();
    return f?-x:x;
}
template<typename T>void print(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)print(x/10);
    putchar(x%10+'0');
}
template<typename T>void print(T x,char ch){
    print(x),putchar(ch);
}

char _[2005][2005],a[2005][2005];
ll ans;

#define left leftt
#define right rightt
int up[2005][2005],down[2005][2005],left[2005][2005],right[2005][2005];
int coefL[2005][2005],coefR[2005][2005];

int iter=0;
void solve(int x1,int x2,int y1,int y2){
    int n=x2-x1+1,m=y2-y1+1;
    if(n<=1||m<=1)return;
    int rot=0;
    if(n>m){
        rep(i,y1,y2)rep(j,x1,x2)a[i-y1][j-x1]=_[j][i];
        swap(n,m);
        rot=1;
    }else{
        rep(i,x1,x2)rep(j,y1,y2)a[i-x1][j-y1]=_[i][j];
        rot=0;
    }
/*    
    if(++iter>=50)return;
    printf("now solve:\n");
    rep(i,0,n-1){
        rep(j,0,m-1)putchar(a[i][j]);
        putchar('\n');
    }
    system("pause");
*/
    rep(i,0,n-1){
        rep(j,0,m-1)left[i][j]=(j&&a[i][j]==a[i][j-1]?left[i][j-1]:j);
        per(j,m-1,0)right[i][j]=(j<m-1&&a[i][j]==a[i][j+1]?right[i][j+1]:j);
    }
    rep(j,0,m-1){
        rep(i,0,n-1)up[i][j]=(i&&a[i][j]==a[i-1][j]?up[i-1][j]:i);
        per(i,n-1,0)down[i][j]=(i<n-1&&a[i][j]==a[i+1][j]?down[i+1][j]:i);
    }
    int mid=m/2-1;
    { // left
        vector d1(n,vector<int> (n)),d2(n,vector<int> (n));
        rep(i,0,n-1){
            int l=left[i][mid],r=mid;
            rep(j,l,r){
                d1[i][i]++;if(down[i][j]<n-1)d1[i][down[i][j]+1]--;
                d2[i][i]++;if(up[i][j]>0)d2[i][up[i][j]-1]--;
            }
            rep(j,1,n-1)d1[i][j]+=d1[i][j-1];
            per(j,n-2,0)d2[i][j]+=d2[i][j+1];
        }
        rep(i,0,n-1){
            rep(j,i+1,n-1){
                if(left[i][mid]>=left[j][mid])coefL[i][j]=d1[i][j];
                else coefL[i][j]=d2[j][i];
            }
        }
    }
    { // right
        vector d1(n,vector<int> (n)),d2(n,vector<int> (n));
        rep(i,0,n-1){
            int l=mid+1,r=right[i][mid+1];
            rep(j,l,r){
                d1[i][i]++;if(down[i][j]<n-1)d1[i][down[i][j]+1]--;
                d2[i][i]++;if(up[i][j]>0)d2[i][up[i][j]-1]--;
            }
            rep(j,1,n-1)d1[i][j]+=d1[i][j-1];
            per(j,n-2,0)d2[i][j]+=d2[i][j+1];
        }
        rep(i,0,n-1){
            rep(j,i+1,n-1){
                if(right[i][mid+1]<=right[j][mid+1])coefR[i][j]=d1[i][j];
                else coefR[i][j]=d2[j][i];
            }
        }
    }
    // combine
    rep(i,0,n-1){
        rep(j,i+1,n-1){
            if(a[i][mid]==a[i][mid+1]&&a[j][mid]==a[j][mid+1]&&a[i][mid]==a[j][mid]){
                ans+=1ll*coefL[i][j]*coefR[i][j];
            }
        }
    }
    if(rot){
        solve(x1,x1+mid,y1,y2);
        solve(x1+mid+1,x2,y1,y2);
    }else{
        solve(x1,x2,y1,y1+mid);
        solve(x1,x2,y1+mid+1,y2);
    }
}

int main(){
    int n=read(),m=read();
    rep(i,0,n-1)scanf("%s",_[i]);
    solve(0,n-1,0,m-1);
    print(ans,'\n');
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 9744kb

input:

3 5
zzzzz
zxzxz
zzzzz

output:

3

result:

ok answer is '3'

Test #2:

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

input:

4 4
abbc
bcca
babc
acbb

output:

0

result:

ok answer is '0'

Test #3:

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

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: 33ms
memory: 14832kb

input:

200 200
aabababbaabbaabaaaabbabaaaaabababbbaaabbbbbbaabbbbbababaabbbabaaaabaaababababababbbbbbabababbbbbababbaababbabaabababbbaabbaaaabbababbaabbaaaaaababbbbbbbbabababbbbababbaaaabbabaaaabaaaababaababaabaabaa
bbabababaabbaaabaaaaabbabbbbbbaabaababaaaabaaaaabbbbbababbaaabbaaabbbaaaabaabbbabbabbaababa...

output:

9063

result:

ok answer is '9063'

Test #5:

score: 0
Accepted
time: 22ms
memory: 15220kb

input:

200 200
bbcacaacbcabaacacbacabcccbbacbbbabaccbcabacbacaccbabcbcbaaacbacbaccbbacabbabbbbaccabcacbccaaaaaabacbcabcacbcacbbcbcbbababcccabccaaacabcbccbcbacccbbbcacacbcbbaccaabcbcababbccbcbacbcaaaacabaccaabacabbca
abbbbaacabcbabacaabcccbbcabaabcaacacacacbabbccbabbcbbcbacbbaababbcbbcacbbbabcbbcbbbbabaaaab...

output:

1993

result:

ok answer is '1993'

Test #6:

score: 0
Accepted
time: 22ms
memory: 15776kb

input:

200 200
daadbcdabdabbcbabacdbdaaabbbdbcbbcdaacababcbbdcdbadbadbbccdcbdbbabbddadaccaaaddacdaddaadaaacbdacbcacbdbcaaddddadcdacaaaaccdaadadaaabadbbdcbcbadccbcabccddaddbcdadbdcddcdbaabaacccdaddcdddcaccbddcdaddcbc
adadabcbbacacdadbbaadbbacaccccaabcadbccdddcdbaabacdcaaccbddaadcbcaadcccdbcdccdacbbbbcbabdcb...

output:

725

result:

ok answer is '725'

Test #7:

score: 0
Accepted
time: 20ms
memory: 14824kb

input:

200 200
txxwjvdrstzdlvxbapbangqherrnvedtncukdffoafsxdpbjhowrytghnpxjdylejgnxmvagxqkgrmektefspdsfzyshkavoputrpszynegndfaxqwuexqhsoqqixyakpshebggckjonwsjaiffhgpimqblmjymlltdanrmkgfpvmuzdntucrrtverpfdeellblawwyk
jieyodnvjkcmuomidegwcrinowmvivwnqvwwffmmhxjktznptunvuxcxanknhevtgchvotjifeutehgbsemomcvtahx...

output:

4

result:

ok answer is '4'

Test #8:

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

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: 3ms
memory: 10364kb

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: 10416kb

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: 4ms
memory: 10324kb

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: 3ms
memory: 10280kb

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: 3ms
memory: 10364kb

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: 3ms
memory: 10284kb

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: 6ms
memory: 10256kb

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: 3ms
memory: 10316kb

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: 10260kb

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: 28ms
memory: 14968kb

input:

200 200
bbbbbbbbaabbaabbbbabbbbbbbbbabbbababbbbbbbbbbbbbbbbabbbabbbbbbabbbbabaaabbbbbbbbbbbbaabbaababbabbbabbbbbbababaabbbbbabbbaabaabbbbbabbabbababbbbbbbaabaababbbababbbbbababbababbbbbbbaababababbbbbabbabbbb
bbbbbbbbbbbbbabbbbbbabaabbaabababbaaaaaabbbbbabbbbabbbbabbbbbabbbbbbababbbbbbbbaabbbbabaaba...

output:

65918

result:

ok answer is '65918'

Test #19:

score: 0
Accepted
time: 23ms
memory: 15288kb

input:

200 200
bbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbabbbbbbbbbabbbbbbabbbbbbbabbbbbbbbbbbbbabbbabbbbbbbbbabbbbbbbabbbabbbbbbbbbbabbbabbbbbbbbbbbbbbaababbbbbbbbbbabbbbaabbbbabbbbbbbbbbbabbbbbbbbbbabbbabbbbabbbbbb
bbbbabbbbbbbbbbbbbbabbbbababbbabbbbbabbbbbbbbbababbabbbbbbbbbbbbababbbbbbbbabbbaaababbbbbbb...

output:

436980

result:

ok answer is '436980'

Test #20:

score: 0
Accepted
time: 22ms
memory: 15116kb

input:

200 200
bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbbbabbbbbbbabbbbab
bbbbbbbbbbabbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbabbbabbab...

output:

2006888

result:

ok answer is '2006888'

Test #21:

score: 0
Accepted
time: 25ms
memory: 15364kb

input:

200 200
bbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbbbbbbbb...

output:

8811371

result:

ok answer is '8811371'

Test #22:

score: 0
Accepted
time: 23ms
memory: 15696kb

input:

200 200
bbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbabbbbbbbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbb...

output:

29949725

result:

ok answer is '29949725'

Test #23:

score: 0
Accepted
time: 28ms
memory: 14616kb

input:

200 200
aabaaaaaaaabaaaaaabaaaaabaaabaaaababaabaabbaabaaaaaaaaaabaaaaaaabaaaaaababaaabbabaaababaababaaaaaaaaaaaabaaaaabaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaababbaaaaaaaaaaaaaaabaaabaabbbbabaaaaaaaaaaaaabaaa
aaaaaaaabbaaaaaaaabbaaaaaabaabbaaaabaaaabbabaaaabaaaaaabaaaaabbbaaaabaaabaaabbababbabbaabaa...

output:

62746

result:

ok answer is '62746'

Test #24:

score: 0
Accepted
time: 22ms
memory: 14920kb

input:

200 200
aabaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaaaaaaaababaabaabaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaabaaabaaaaaaaabaaaaaabaaaaaaaaaaaaaaabaabaaaabaaaaaaaaabaaabaaaaaaaaaaaabaaaaaabbaaaabaaaa
aabaaaaabaabaaaaaaababaaabaaaaaaabaaaaaaaaaaaaaaaaabbabaaaaaaaaaaaaaaaaaaaaaaababaabbaabaab...

output:

393455

result:

ok answer is '393455'

Test #25:

score: 0
Accepted
time: 22ms
memory: 14740kb

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaababaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaa...

output:

1744602

result:

ok answer is '1744602'

Test #26:

score: 0
Accepted
time: 23ms
memory: 14932kb

input:

200 200
aaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaa...

output:

7733272

result:

ok answer is '7733272'

Test #27:

score: 0
Accepted
time: 20ms
memory: 15928kb

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaa...

output:

26388726

result:

ok answer is '26388726'

Test #28:

score: 0
Accepted
time: 2473ms
memory: 132736kb

input:

2000 2000
hxbcuprmlgnupldnbzhcpesdlawilpqilczdvavjoetwdjtjkcdccftawgagfjhfcnkejypkgwswgiibgfxzzcgjdqjmamdkttedmffqievedyicgurwmungupmvuwralxutfnrykylbqrbqquvrchuuoebfapvgsjgasdfnkxrjnflizeqychfhuetijdnuoenucqkktzkurqcpusbncvilxziylxxyprsqwcdrgcviobiapvuxvhignilpavhjuebiwhatxtqvemtmxwlufvdkmqstjpqvos...

output:

238

result:

ok answer is '238'

Test #29:

score: 0
Accepted
time: 3367ms
memory: 132692kb

input:

2000 2000
aabbbabababbbbbbbaabbaabbbbabbaabbbbbbbbabbaabbabaababababbbbbbabaaabbbbbabbaabbaabbaaaabaaabaaaaaabbbbaaaaabbbbabbaaaababbaaaabbaabaababaaaabaaaaaabbbaabaabbbbbabaaaaaaabaaabbaabaababaaabbbaababababaabbbbbaabbbaabaaabbbbaababaaabaaabbaabaaaaaababbabbaaabbbababaabaabaabbbaabaabbbbbaaababbb...

output:

888377

result:

ok answer is '888377'

Test #30:

score: 0
Accepted
time: 129ms
memory: 13172kb

input:

100 2000
baaabbabbaaababaaababbbabbabaaaabbbbbbbbabababbaabaabaaaaaaaabbbbbaaaaaaaaaabaabbbaabaabaaabaaaababbbbbaaaaabbbaaabbbaababbaaaaabbabaaaaaaaabaabaabbbbbbbbbaaabaababbaaabbbaabbaaaaaaabbbabaaabbabbbaaaabbabbababbaaaabbabbaaaaaababbbbababaabbabbabbbbbabbaababbabbbaabbbaabbababbbabbabbaaabbbbbb...

output:

44364

result:

ok answer is '44364'

Test #31:

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

input:

3 2000
abaabbbbaaabbbaaaababaaaabbbbaaaaabaabbaaaabbaaaaabababaababababbbabbbabbbabbbbbabaaabaabaabbaaabaaabbabbaabbabbbbabaabbabbbaabbbbbabbabbbababaaaabaabaabaaaabaabaabaaaaabbababbbbbaabbabbaababbbaaababaaaaaaababbbabbaabbabbbababaababababbabbbababbbaabbabaaaabbaabaaaabbaabbabaabaababbababbbabaab...

output:

771

result:

ok answer is '771'

Test #32:

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

input:

2 2000
aabaabaaabbbbaababbaaabbabaaaaabaaabbbabababaaaaabaabbaababaaabbaaaabaabaababbabbbbaaabbbbbaabaaaabbaababbaabaaabbbbbbaaaaabababbaaaababbbabbbbaabbbbaabaaaaaaaaaaabbbabaaaaaabababaaaaabbaaababaabababababaabbbabaababbbabbaaaaabbabbaaaaaabbbbaabaaabbaabaaabbbbbaabaaabaaaaaabbaababbaaaaabbabbbba...

output:

309

result:

ok answer is '309'

Test #33:

score: 0
Accepted
time: 3220ms
memory: 132688kb

input:

2000 2000
bbbbbbbbbababbbbbbbbbbabbabbbbbbbabbbbbbbbbababaaabbaabbbbaabbaababbbaabaabbabbbbbaaababbbabbabbbbbbabbbbbababbabbabababaabbbbabbbbabbabbbabbbabbbbabbbbabbabaaabbbbaabaababbbbbbaabaabbbbabbbbaaabbbbbaabbabbaabababaabbbbbbbbbbababaababbbbbbbbbbababaabbbaabbbbbbbbbbbbbabbbaaabaabbbbbabbbabbb...

output:

6611891

result:

ok answer is '6611891'

Test #34:

score: 0
Accepted
time: 3066ms
memory: 132640kb

input:

2000 2000
bbabbbbbabbbbbbbababbabbbbbbbbabbbbbbabbabbbababbbbbbbbbbbbbabbbbbbbbbbbbabbbababbbbbbbbbbbbbbbbbbbabbbbabbbbabbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbabbbbbbabbbbbbbbbbabaababaabbbbbbbbbbbbbbbbbbabbbbabbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbabbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

42485356

result:

ok answer is '42485356'

Test #35:

score: 0
Accepted
time: 2906ms
memory: 132692kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbabbbbbabbbbbbaabbabbbbbabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbb...

output:

208474291

result:

ok answer is '208474291'

Test #36:

score: 0
Accepted
time: 2864ms
memory: 132688kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbababbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

920144952

result:

ok answer is '920144952'

Test #37:

score: 0
Accepted
time: 2762ms
memory: 132736kb

input:

2000 2000
bbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3800182739

result:

ok answer is '3800182739'

Test #38:

score: 0
Accepted
time: 3210ms
memory: 132784kb

input:

2000 2000
aaaabbabbabaaaaabaaaaabbaaaabaabaabaaaaaaaaaaaabaababaaabbaabaababaaaaaaabaabaaabbbabaaaaabaaaabaaaaaaaaaaaaabaaaaaaaabbaaaabaaaaaaaaaabbbaabaabaaaaaabaaaaabbaaaaababaaaaaabbaaaaaaabaaaaaabaaaaabbbaaaaaaaaabbbababaaaaaaaaaabaaaaaaaaaaaaaababababaaaaaaaabbaaabaaabbaabbaaaaababaaaaaabaaaabaa...

output:

6633997

result:

ok answer is '6633997'

Test #39:

score: 0
Accepted
time: 3026ms
memory: 132616kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaabaaaabaaaaababbaaaabaaaababaaaaaaabaaaaaaaaaaaaaabaaabaaaaaabaaaaaaaaaaaabbaaabaaaaababaababaaaaabababaaaaabaaaaaaaaaaabaabbaaaabaaaaaaaabaaaaaaaaaaaaaaaabbaaaaaaaabaaaaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaabaaaaaaabaaaaaaaaaabaaaaaaaaabbabaaaaababaabaabaaaaaaaa...

output:

42677036

result:

ok answer is '42677036'

Test #40:

score: 0
Accepted
time: 2888ms
memory: 132732kb

input:

2000 2000
aaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaabaaabaaaaabaaaaaaaaaaaaaabaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaabaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaa...

output:

209624629

result:

ok answer is '209624629'

Test #41:

score: 0
Accepted
time: 2830ms
memory: 132600kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaba...

output:

908496629

result:

ok answer is '908496629'

Test #42:

score: 0
Accepted
time: 2734ms
memory: 132692kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3819264516

result:

ok answer is '3819264516'

Test #43:

score: 0
Accepted
time: 2540ms
memory: 132684kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2193746696652

result:

ok answer is '2193746696652'

Test #44:

score: 0
Accepted
time: 2532ms
memory: 132636kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2886592675758

result:

ok answer is '2886592675758'

Test #45:

score: 0
Accepted
time: 2510ms
memory: 132740kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3460768674956

result:

ok answer is '3460768674956'

Test #46:

score: 0
Accepted
time: 2516ms
memory: 132840kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3680478183757

result:

ok answer is '3680478183757'

Test #47:

score: 0
Accepted
time: 2488ms
memory: 132692kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3834982314152

result:

ok answer is '3834982314152'

Test #48:

score: 0
Accepted
time: 2567ms
memory: 132836kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2113716926482

result:

ok answer is '2113716926482'

Test #49:

score: 0
Accepted
time: 2486ms
memory: 132688kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2884992951736

result:

ok answer is '2884992951736'

Test #50:

score: 0
Accepted
time: 2475ms
memory: 132784kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3434267490537

result:

ok answer is '3434267490537'

Test #51:

score: 0
Accepted
time: 2539ms
memory: 132636kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3693371002932

result:

ok answer is '3693371002932'

Test #52:

score: 0
Accepted
time: 2553ms
memory: 132836kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3833465918348

result:

ok answer is '3833465918348'

Test #53:

score: 0
Accepted
time: 2526ms
memory: 132504kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #54:

score: 0
Accepted
time: 2493ms
memory: 132840kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #55:

score: 0
Accepted
time: 27ms
memory: 10440kb

input:

20 2000
bbbbbabbbabbbbbabbbbbbbbaaaabaabbaabbbbaabbbabbabbabbaabbbabbabbabbbbbbaabbbbbababbabbbbbbabbbbbbbbbbbaabbabbbbbaababbbbbbbbabbbabbbbbbbabbbbbbbbbabbbabbabbbbaababbbbbbbbaabbbabbbbbbbbbabbbaabbbaabbbbbababbbbbbbbabbbbbbbabbbbbbbbabbbbbababbbbbbbbbbbbbbbbababbbbbbbbbbbaaabbabbbbabbbbbaabbbbab...

output:

56816

result:

ok answer is '56816'

Test #56:

score: 0
Accepted
time: 25ms
memory: 10336kb

input:

20 2000
bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbababbabbabbabbbbabbbbbbabbbabbbbbabbbbabbbbbabbbbbbabbbbbbbbbbbbaabbabbbbababbbabbbbbbbbbbabbbabbbbbbbbbbbbbbbaabbabbbbbbbbbbbbbbabbbbabbabbbbbbbabbabbbbbbbbbbbabbbbabbbaabbaaabbbbbbbabbbbbbbbbbbbbabbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbabbbb...

output:

355419

result:

ok answer is '355419'

Test #57:

score: 0
Accepted
time: 24ms
memory: 10476kb

input:

20 2000
abbbbbabbbabbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbaabbbbbb...

output:

1290507

result:

ok answer is '1290507'

Test #58:

score: 0
Accepted
time: 18ms
memory: 10544kb

input:

20 2000
abbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbb...

output:

3673870

result:

ok answer is '3673870'

Test #59:

score: 0
Accepted
time: 18ms
memory: 10544kb

input:

20 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

9771068

result:

ok answer is '9771068'

Test #60:

score: 0
Accepted
time: 23ms
memory: 10544kb

input:

20 2000
babaabaaaababaaabaaaaaaaaaaaabaaaabaaaaaabbaababaababaaaaaaaaaaaaaabaaaaaaaabaaaaaabbaaaaaaababaaaaaaabaaabaaaababaaaabaaaabbbababaaaaaababaaababaaaaaaaabaaaaaaabaaababaaabaaaaaaababaabaaaaaabaaaaaaaaaaaabaaaaaaaaabaabbaaaababaaaaaabaaaababaaaaabaabbabaaabbaaaabaaaaababababaabaabaaaaabaabaaa...

output:

57804

result:

ok answer is '57804'

Test #61:

score: 0
Accepted
time: 25ms
memory: 10552kb

input:

20 2000
aaaaaaaaaaabaaabaaabaaaaabbbaaaaaaaabaaaaaaaabaabaaaaaabaaaaabababbaaaaaabaaaaaaabbabaaaaaaaaaaaaaabaaaaaaababaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaababaaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaabaaaaaaabaaabaaabaaabaabaaabaaaaaaabbaaaaabaabaaaabaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaa...

output:

361169

result:

ok answer is '361169'

Test #62:

score: 0
Accepted
time: 19ms
memory: 10440kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaababaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaa...

output:

1287432

result:

ok answer is '1287432'

Test #63:

score: 0
Accepted
time: 22ms
memory: 10456kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba...

output:

3785925

result:

ok answer is '3785925'

Test #64:

score: 0
Accepted
time: 22ms
memory: 10460kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

9744215

result:

ok answer is '9744215'

Test #65:

score: 0
Accepted
time: 20ms
memory: 11464kb

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: 19ms
memory: 12412kb

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: 20ms
memory: 10916kb

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: 17ms
memory: 12392kb

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: 18ms
memory: 11880kb

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: 24ms
memory: 11984kb

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: 18ms
memory: 10812kb

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: 25ms
memory: 11056kb

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: 19ms
memory: 12500kb

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: 19ms
memory: 11972kb

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: 2520ms
memory: 132840kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaa...

output:

2191400000

result:

ok answer is '2191400000'

Test #76:

score: 0
Accepted
time: 2445ms
memory: 132696kb

input:

2000 2000
ccccccccccccccccccccaaaaaaaaaaaaaaaaaaaavvvvvvvvvvvvvvvvvvvvppppppppppppppppppppvvvvvvvvvvvvvvvvvvvvttttttttttttttttttttvvvvvvvvvvvvvvvvvvvvoooooooooooooooooooorrrrrrrrrrrrrrrrrrrrnnnnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaajjjjjjjjjjjjjjjjjjjjrrrrrrrrrrrrrrrrrrrrwwwwwwwwwwwwwwwwwwwwiiiiiiiiii...

output:

416024000

result:

ok answer is '416024000'

Test #77:

score: 0
Accepted
time: 2481ms
memory: 132680kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

151925000000

result:

ok answer is '151925000000'

Test #78:

score: 0
Accepted
time: 2437ms
memory: 132780kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

45969000000

result:

ok answer is '45969000000'

Test #79:

score: 0
Accepted
time: 2572ms
memory: 132784kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

536440500

result:

ok answer is '536440500'

Test #80:

score: 0
Accepted
time: 2489ms
memory: 132664kb

input:

2000 2000
ddddddddddkkkkkkkkkkrrrrrrrrrrwwwwwwwwwwvvvvvvvvvvaaaaaaaaaaoooooooooottttttttttttttttttttzzzzzzzzzzqqqqqqqqqqssssssssssuuuuuuuuuuuuuuuuuuuuxxxxxxxxxxnnnnnnnnnnuuuuuuuuuuzzzzzzzzzzeeeeeeeeeeuuuuuuuuuubbbbbbbbbbnnnnnnnnnnmmmmmmmmmmccccccccccppppppppppnnnnnnnnnnhhhhhhhhhhllllllllllgggggggggg...

output:

95748500

result:

ok answer is '95748500'

Test #81:

score: 0
Accepted
time: 2493ms
memory: 132780kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

49867000000

result:

ok answer is '49867000000'

Test #82:

score: 0
Accepted
time: 2436ms
memory: 132640kb

input:

2000 2000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

10989000000

result:

ok answer is '10989000000'

Test #83:

score: 0
Accepted
time: 2491ms
memory: 132836kb

input:

2000 2000
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

998001000000

result:

ok answer is '998001000000'

Test #84:

score: 0
Accepted
time: 2470ms
memory: 132680kb

input:

2000 2000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

249001000000

result:

ok answer is '249001000000'

Test #85:

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

input:

1 1
b

output:

0

result:

ok answer is '0'

Test #86:

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

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: 4ms
memory: 8972kb

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: 4ms
memory: 8540kb

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: 2ms
memory: 9440kb

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: 3ms
memory: 5816kb

input:

1 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #91:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #92:

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

input:

1 2000
bbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #93:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #94:

score: 0
Accepted
time: 1ms
memory: 5736kb

input:

1 2000
bbaaabbbabbbbabbbbbbbaaaabbabbbababbbbabaaaaababbabbbbbaabbbaababbabbbaaabaaabaabbabbababbbabbbbbbaabbbbbaaabbbaabababaaaaabbbaabbbaabbbaaaabbbbaaaababbbababaabaabbaabbabaaabaaaaababaaaabaaabababbbbbaababbaabaababbaababababbabaaababbaaabbbbabbbbbabbabbbaabbbaaaaaaaaaaabbabbbaaababbaababababba...

output:

0

result:

ok answer is '0'

Test #95:

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

input:

1 2000
ybznxtzkzdspabhllysnjejgxhynartagoluiafvuzylklphybjbgbydzwviwrjqqcocnryvxzhilkcbzljokipgrdvilnghahtznvxlfofzrhzqwotlfgeyaratruepvpnfianhskanisdjwmekyahnaaeagdxtplxxudezjkusekalweqvvkaghkhbewxufzucflhkkwjcfikolebosrreyfdoxwgjlqvtvmmbykpzlelzoufjtskvkhilfuesudaugjalzhsjmnxhauphiglkrfpigxueotfds...

output:

0

result:

ok answer is '0'

Test #96:

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

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: 4ms
memory: 8116kb

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'