QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#786068#1088. Border Similarity Undertakingsunzz3183AC ✓560ms145212kbC++143.1kb2024-11-26 20:08:262024-11-26 20:08:28

Judging History

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

  • [2024-11-26 20:08:28]
  • 评测
  • 测评结果:AC
  • 用时:560ms
  • 内存:145212kb
  • [2024-11-26 20:08:26]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
    char ch=getchar();int x=0;bool f=1;
    while(ch<'0'||'9'<ch){if(ch=='-')f=0;ch=getchar();}
    while('0'<=ch&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return f?x:-x;
}
const int N=2502;
mt19937 rnd(3183);
int n,m,U[N][N],D[N][N],L[N][N],R[N][N],pre[N][N],suf[N][N];
char s[N][N],c[N][N];
ll ans;
void solve(int u,int d,int l,int r){
    if(l==r||u==d)return;
    if(r-l>=d-u){
        int mid=(l+r)>>1;
        solve(u,d,l,mid);solve(u,d,mid+1,r);
        for(int i=u;i<=d;i++)
            for(int j=u;j<=d;j++)pre[i][j]=suf[i][j]=0;
        for(int i=u;i<=d;i++){
            for(int j=mid;j>=l&&j>=L[i][mid];j--)
                pre[i][min(D[i][j],d)]++,pre[i][max(U[i][j],u)]++;
            for(int j=d-1;j>=i;j--)pre[i][j]+=pre[i][j+1];
            for(int j=u+1;j<=i;j++)pre[i][j]+=pre[i][j-1];
            for(int j=mid+1;j<=r&&j<=R[i][mid+1];j++)
                suf[i][min(D[i][j],d)]++,suf[i][max(U[i][j],u)]++;
            for(int j=d-1;j>=i;j--)suf[i][j]+=suf[i][j+1];
            for(int j=u+1;j<=i;j++)suf[i][j]+=suf[i][j-1];
        }
        for(int i=u;i<=d;i++)
            for(int j=i+1;j<=d;j++)
                if(s[i][mid]==s[j][mid]&&s[i][mid]==s[i][mid+1]&&s[i][mid]==s[j][mid+1]){
                    int cntL=L[i][mid]>=L[j][mid]?pre[i][j]:pre[j][i];
                    int cntR=R[i][mid+1]<=R[j][mid+1]?suf[i][j]:suf[j][i];
                    ans+=1ll*cntL*cntR;
                }
    }
    else{
        int mid=(u+d)>>1;
        solve(u,mid,l,r);solve(mid+1,d,l,r);
        for(int i=l;i<=r;i++)
            for(int j=l;j<=r;j++)pre[i][j]=suf[i][j]=0;
        for(int i=l;i<=r;i++){
            for(int j=mid;j>=u&&j>=U[mid][i];j--)
                pre[i][min(R[j][i],r)]++,pre[i][max(L[j][i],l)]++;
            for(int j=r-1;j>=i;j--)pre[i][j]+=pre[i][j+1];
            for(int j=l+1;j<=i;j++)pre[i][j]+=pre[i][j-1];
            for(int j=mid+1;j<=d&&j<=D[mid+1][i];j++)
                suf[i][min(R[j][i],r)]++,suf[i][max(L[j][i],l)]++;
            for(int j=r-1;j>=i;j--)suf[i][j]+=suf[i][j+1];
            for(int j=l+1;j<=i;j++)suf[i][j]+=suf[i][j-1];
        }
        for(int i=l;i<=r;i++)
            for(int j=i+1;j<=r;j++)
                if(s[mid][i]==s[mid][j]&&s[mid][i]==s[mid+1][i]&&s[mid][i]==s[mid+1][j]){
                    int cntL=U[mid][i]>=U[mid][j]?pre[i][j]:pre[j][i];
                    int cntR=D[mid+1][i]<=D[mid+1][j]?suf[i][j]:suf[j][i];
                    ans+=1ll*cntL*cntR;
                }
    }
}
signed main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            U[i][j]=(s[i][j]==s[i-1][j]?U[i-1][j]:i),
            L[i][j]=(s[i][j]==s[i][j-1]?L[i][j-1]:j);
    for(int i=n;i;i--)
        for(int j=m;j;j--)
            D[i][j]=(s[i][j]==s[i+1][j]?D[i+1][j]:i),
            R[i][j]=(s[i][j]==s[i][j+1]?R[i][j+1]:j);
    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: 18296kb

input:

3 5
zzzzz
zxzxz
zzzzz

output:

3

result:

ok answer is '3'

Test #2:

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

input:

4 4
abbc
bcca
babc
acbb

output:

0

result:

ok answer is '0'

Test #3:

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

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

input:

200 200
aabababbaabbaabaaaabbabaaaaabababbbaaabbbbbbaabbbbbababaabbbabaaaabaaababababababbbbbbabababbbbbababbaababbabaabababbbaabbaaaabbababbaabbaaaaaababbbbbbbbabababbbbababbaaaabbabaaaabaaaababaababaabaabaa
bbabababaabbaaabaaaaabbabbbbbbaabaababaaaabaaaaabbbbbababbaaabbaaabbbaaaabaabbbabbabbaababa...

output:

9063

result:

ok answer is '9063'

Test #5:

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

input:

200 200
bbcacaacbcabaacacbacabcccbbacbbbabaccbcabacbacaccbabcbcbaaacbacbaccbbacabbabbbbaccabcacbccaaaaaabacbcabcacbcacbbcbcbbababcccabccaaacabcbccbcbacccbbbcacacbcbbaccaabcbcababbccbcbacbcaaaacabaccaabacabbca
abbbbaacabcbabacaabcccbbcabaabcaacacacacbabbccbabbcbbcbacbbaababbcbbcacbbbabcbbcbbbbabaaaab...

output:

1993

result:

ok answer is '1993'

Test #6:

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

input:

200 200
daadbcdabdabbcbabacdbdaaabbbdbcbbcdaacababcbbdcdbadbadbbccdcbdbbabbddadaccaaaddacdaddaadaaacbdacbcacbdbcaaddddadcdacaaaaccdaadadaaabadbbdcbcbadccbcabccddaddbcdadbdcddcdbaabaacccdaddcdddcaccbddcdaddcbc
adadabcbbacacdadbbaadbbacaccccaabcadbccdddcdbaabacdcaaccbddaadcbcaadcccdbcdccdacbbbbcbabdcb...

output:

725

result:

ok answer is '725'

Test #7:

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

input:

200 200
txxwjvdrstzdlvxbapbangqherrnvedtncukdffoafsxdpbjhowrytghnpxjdylejgnxmvagxqkgrmektefspdsfzyshkavoputrpszynegndfaxqwuexqhsoqqixyakpshebggckjonwsjaiffhgpimqblmjymlltdanrmkgfpvmuzdntucrrtverpfdeellblawwyk
jieyodnvjkcmuomidegwcrinowmvivwnqvwwffmmhxjktznptunvuxcxanknhevtgchvotjifeutehgbsemomcvtahx...

output:

4

result:

ok answer is '4'

Test #8:

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

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

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

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

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

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: 0ms
memory: 28452kb

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

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

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

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

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

input:

200 200
bbbbbbbbaabbaabbbbabbbbbbbbbabbbababbbbbbbbbbbbbbbbabbbabbbbbbabbbbabaaabbbbbbbbbbbbaabbaababbabbbabbbbbbababaabbbbbabbbaabaabbbbbabbabbababbbbbbbaabaababbbababbbbbababbababbbbbbbaababababbbbbabbabbbb
bbbbbbbbbbbbbabbbbbbabaabbaabababbaaaaaabbbbbabbbbabbbbabbbbbabbbbbbababbbbbbbbaabbbbabaaba...

output:

65918

result:

ok answer is '65918'

Test #19:

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

input:

200 200
bbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbabbbbbbbbbabbbbbbabbbbbbbabbbbbbbbbbbbbabbbabbbbbbbbbabbbbbbbabbbabbbbbbbbbbabbbabbbbbbbbbbbbbbaababbbbbbbbbbabbbbaabbbbabbbbbbbbbbbabbbbbbbbbbabbbabbbbabbbbbb
bbbbabbbbbbbbbbbbbbabbbbababbbabbbbbabbbbbbbbbababbabbbbbbbbbbbbababbbbbbbbabbbaaababbbbbbb...

output:

436980

result:

ok answer is '436980'

Test #20:

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

input:

200 200
bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbbbabbbbbbbabbbbab
bbbbbbbbbbabbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbabbbabbab...

output:

2006888

result:

ok answer is '2006888'

Test #21:

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

input:

200 200
bbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbbbbbbbb...

output:

8811371

result:

ok answer is '8811371'

Test #22:

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

input:

200 200
bbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbabbbbbbbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbb...

output:

29949725

result:

ok answer is '29949725'

Test #23:

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

input:

200 200
aabaaaaaaaabaaaaaabaaaaabaaabaaaababaabaabbaabaaaaaaaaaabaaaaaaabaaaaaababaaabbabaaababaababaaaaaaaaaaaabaaaaabaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaababbaaaaaaaaaaaaaaabaaabaabbbbabaaaaaaaaaaaaabaaa
aaaaaaaabbaaaaaaaabbaaaaaabaabbaaaabaaaabbabaaaabaaaaaabaaaaabbbaaaabaaabaaabbababbabbaabaa...

output:

62746

result:

ok answer is '62746'

Test #24:

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

input:

200 200
aabaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaaaaaaaababaabaabaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaabaaabaaaaaaaabaaaaaabaaaaaaaaaaaaaaabaabaaaabaaaaaaaaabaaabaaaaaaaaaaaabaaaaaabbaaaabaaaa
aabaaaaabaabaaaaaaababaaabaaaaaaabaaaaaaaaaaaaaaaaabbabaaaaaaaaaaaaaaaaaaaaaaababaabbaabaab...

output:

393455

result:

ok answer is '393455'

Test #25:

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

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaababaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaa...

output:

1744602

result:

ok answer is '1744602'

Test #26:

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

input:

200 200
aaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaa...

output:

7733272

result:

ok answer is '7733272'

Test #27:

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

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaa...

output:

26388726

result:

ok answer is '26388726'

Test #28:

score: 0
Accepted
time: 232ms
memory: 134956kb

input:

2000 2000
hxbcuprmlgnupldnbzhcpesdlawilpqilczdvavjoetwdjtjkcdccftawgagfjhfcnkejypkgwswgiibgfxzzcgjdqjmamdkttedmffqievedyicgurwmungupmvuwralxutfnrykylbqrbqquvrchuuoebfapvgsjgasdfnkxrjnflizeqychfhuetijdnuoenucqkktzkurqcpusbncvilxziylxxyprsqwcdrgcviobiapvuxvhignilpavhjuebiwhatxtqvemtmxwlufvdkmqstjpqvos...

output:

238

result:

ok answer is '238'

Test #29:

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

input:

2000 2000
aabbbabababbbbbbbaabbaabbbbabbaabbbbbbbbabbaabbabaababababbbbbbabaaabbbbbabbaabbaabbaaaabaaabaaaaaabbbbaaaaabbbbabbaaaababbaaaabbaabaababaaaabaaaaaabbbaabaabbbbbabaaaaaaabaaabbaabaababaaabbbaababababaabbbbbaabbbaabaaabbbbaababaaabaaabbaabaaaaaababbabbaaabbbababaabaabaabbbaabaabbbbbaaababbb...

output:

888377

result:

ok answer is '888377'

Test #30:

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

input:

100 2000
baaabbabbaaababaaababbbabbabaaaabbbbbbbbabababbaabaabaaaaaaaabbbbbaaaaaaaaaabaabbbaabaabaaabaaaababbbbbaaaaabbbaaabbbaababbaaaaabbabaaaaaaaabaabaabbbbbbbbbaaabaababbaaabbbaabbaaaaaaabbbabaaabbabbbaaaabbabbababbaaaabbabbaaaaaababbbbababaabbabbabbbbbabbaababbabbbaabbbaabbababbbabbabbaaabbbbbb...

output:

44364

result:

ok answer is '44364'

Test #31:

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

input:

3 2000
abaabbbbaaabbbaaaababaaaabbbbaaaaabaabbaaaabbaaaaabababaababababbbabbbabbbabbbbbabaaabaabaabbaaabaaabbabbaabbabbbbabaabbabbbaabbbbbabbabbbababaaaabaabaabaaaabaabaabaaaaabbababbbbbaabbabbaababbbaaababaaaaaaababbbabbaabbabbbababaababababbabbbababbbaabbabaaaabbaabaaaabbaabbabaabaababbababbbabaab...

output:

771

result:

ok answer is '771'

Test #32:

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

input:

2 2000
aabaabaaabbbbaababbaaabbabaaaaabaaabbbabababaaaaabaabbaababaaabbaaaabaabaababbabbbbaaabbbbbaabaaaabbaababbaabaaabbbbbbaaaaabababbaaaababbbabbbbaabbbbaabaaaaaaaaaaabbbabaaaaaabababaaaaabbaaababaabababababaabbbabaababbbabbaaaaabbabbaaaaaabbbbaabaaabbaabaaabbbbbaabaaabaaaaaabbaababbaaaaabbabbbba...

output:

309

result:

ok answer is '309'

Test #33:

score: 0
Accepted
time: 518ms
memory: 140980kb

input:

2000 2000
bbbbbbbbbababbbbbbbbbbabbabbbbbbbabbbbbbbbbababaaabbaabbbbaabbaababbbaabaabbabbbbbaaababbbabbabbbbbbabbbbbababbabbabababaabbbbabbbbabbabbbabbbabbbbabbbbabbabaaabbbbaabaababbbbbbaabaabbbbabbbbaaabbbbbaabbabbaabababaabbbbbbbbbbababaababbbbbbbbbbababaabbbaabbbbbbbbbbbbbabbbaaabaabbbbbabbbabbb...

output:

6611891

result:

ok answer is '6611891'

Test #34:

score: 0
Accepted
time: 531ms
memory: 145112kb

input:

2000 2000
bbabbbbbabbbbbbbababbabbbbbbbbabbbbbbabbabbbababbbbbbbbbbbbbabbbbbbbbbbbbabbbababbbbbbbbbbbbbbbbbbbabbbbabbbbabbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbabbbbbbabbbbbbbbbbabaababaabbbbbbbbbbbbbbbbbbabbbbabbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbabbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

42485356

result:

ok answer is '42485356'

Test #35:

score: 0
Accepted
time: 533ms
memory: 141088kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbabbbbbabbbbbbaabbabbbbbabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbb...

output:

208474291

result:

ok answer is '208474291'

Test #36:

score: 0
Accepted
time: 546ms
memory: 143088kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbababbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

920144952

result:

ok answer is '920144952'

Test #37:

score: 0
Accepted
time: 539ms
memory: 141104kb

input:

2000 2000
bbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3800182739

result:

ok answer is '3800182739'

Test #38:

score: 0
Accepted
time: 525ms
memory: 139064kb

input:

2000 2000
aaaabbabbabaaaaabaaaaabbaaaabaabaabaaaaaaaaaaaabaababaaabbaabaababaaaaaaabaabaaabbbabaaaaabaaaabaaaaaaaaaaaaabaaaaaaaabbaaaabaaaaaaaaaabbbaabaabaaaaaabaaaaabbaaaaababaaaaaabbaaaaaaabaaaaaabaaaaabbbaaaaaaaaabbbababaaaaaaaaaabaaaaaaaaaaaaaababababaaaaaaaabbaaabaaabbaabbaaaaababaaaaaabaaaabaa...

output:

6633997

result:

ok answer is '6633997'

Test #39:

score: 0
Accepted
time: 526ms
memory: 139044kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaabaaaabaaaaababbaaaabaaaababaaaaaaabaaaaaaaaaaaaaabaaabaaaaaabaaaaaaaaaaaabbaaabaaaaababaababaaaaabababaaaaabaaaaaaaaaaabaabbaaaabaaaaaaaabaaaaaaaaaaaaaaaabbaaaaaaaabaaaaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaabaaaaaaabaaaaaaaaaabaaaaaaaaabbabaaaaababaabaabaaaaaaaa...

output:

42677036

result:

ok answer is '42677036'

Test #40:

score: 0
Accepted
time: 525ms
memory: 132792kb

input:

2000 2000
aaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaabaaabaaaaabaaaaaaaaaaaaaabaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaabaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaa...

output:

209624629

result:

ok answer is '209624629'

Test #41:

score: 0
Accepted
time: 536ms
memory: 141028kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaba...

output:

908496629

result:

ok answer is '908496629'

Test #42:

score: 0
Accepted
time: 560ms
memory: 139036kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3819264516

result:

ok answer is '3819264516'

Test #43:

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

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2193746696652

result:

ok answer is '2193746696652'

Test #44:

score: 0
Accepted
time: 472ms
memory: 143180kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2886592675758

result:

ok answer is '2886592675758'

Test #45:

score: 0
Accepted
time: 481ms
memory: 143220kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3460768674956

result:

ok answer is '3460768674956'

Test #46:

score: 0
Accepted
time: 453ms
memory: 145188kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3680478183757

result:

ok answer is '3680478183757'

Test #47:

score: 0
Accepted
time: 453ms
memory: 134964kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3834982314152

result:

ok answer is '3834982314152'

Test #48:

score: 0
Accepted
time: 470ms
memory: 134956kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2113716926482

result:

ok answer is '2113716926482'

Test #49:

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

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2884992951736

result:

ok answer is '2884992951736'

Test #50:

score: 0
Accepted
time: 446ms
memory: 132828kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3434267490537

result:

ok answer is '3434267490537'

Test #51:

score: 0
Accepted
time: 448ms
memory: 143168kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3693371002932

result:

ok answer is '3693371002932'

Test #52:

score: 0
Accepted
time: 460ms
memory: 145212kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3833465918348

result:

ok answer is '3833465918348'

Test #53:

score: 0
Accepted
time: 435ms
memory: 139064kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #54:

score: 0
Accepted
time: 440ms
memory: 143152kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #55:

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

input:

20 2000
bbbbbabbbabbbbbabbbbbbbbaaaabaabbaabbbbaabbbabbabbabbaabbbabbabbabbbbbbaabbbbbababbabbbbbbabbbbbbbbbbbaabbabbbbbaababbbbbbbbabbbabbbbbbbabbbbbbbbbabbbabbabbbbaababbbbbbbbaabbbabbbbbbbbbabbbaabbbaabbbbbababbbbbbbbabbbbbbbabbbbbbbbabbbbbababbbbbbbbbbbbbbbbababbbbbbbbbbbaaabbabbbbabbbbbaabbbbab...

output:

56816

result:

ok answer is '56816'

Test #56:

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

input:

20 2000
bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbababbabbabbabbbbabbbbbbabbbabbbbbabbbbabbbbbabbbbbbabbbbbbbbbbbbaabbabbbbababbbabbbbbbbbbbabbbabbbbbbbbbbbbbbbaabbabbbbbbbbbbbbbbabbbbabbabbbbbbbabbabbbbbbbbbbbabbbbabbbaabbaaabbbbbbbabbbbbbbbbbbbbabbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbabbbb...

output:

355419

result:

ok answer is '355419'

Test #57:

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

input:

20 2000
abbbbbabbbabbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbaabbbbbb...

output:

1290507

result:

ok answer is '1290507'

Test #58:

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

input:

20 2000
abbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbb...

output:

3673870

result:

ok answer is '3673870'

Test #59:

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

input:

20 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

9771068

result:

ok answer is '9771068'

Test #60:

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

input:

20 2000
babaabaaaababaaabaaaaaaaaaaaabaaaabaaaaaabbaababaababaaaaaaaaaaaaaabaaaaaaaabaaaaaabbaaaaaaababaaaaaaabaaabaaaababaaaabaaaabbbababaaaaaababaaababaaaaaaaabaaaaaaabaaababaaabaaaaaaababaabaaaaaabaaaaaaaaaaaabaaaaaaaaabaabbaaaababaaaaaabaaaababaaaaabaabbabaaabbaaaabaaaaababababaabaabaaaaabaabaaa...

output:

57804

result:

ok answer is '57804'

Test #61:

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

input:

20 2000
aaaaaaaaaaabaaabaaabaaaaabbbaaaaaaaabaaaaaaaabaabaaaaaabaaaaabababbaaaaaabaaaaaaabbabaaaaaaaaaaaaaabaaaaaaababaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaababaaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaabaaaaaaabaaabaaabaaabaabaaabaaaaaaabbaaaaabaabaaaabaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaa...

output:

361169

result:

ok answer is '361169'

Test #62:

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

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaababaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaa...

output:

1287432

result:

ok answer is '1287432'

Test #63:

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

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba...

output:

3785925

result:

ok answer is '3785925'

Test #64:

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

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

9744215

result:

ok answer is '9744215'

Test #65:

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

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

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

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

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

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

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: 0ms
memory: 145204kb

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

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

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

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: 341ms
memory: 134912kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaa...

output:

2191400000

result:

ok answer is '2191400000'

Test #76:

score: 0
Accepted
time: 309ms
memory: 132792kb

input:

2000 2000
ccccccccccccccccccccaaaaaaaaaaaaaaaaaaaavvvvvvvvvvvvvvvvvvvvppppppppppppppppppppvvvvvvvvvvvvvvvvvvvvttttttttttttttttttttvvvvvvvvvvvvvvvvvvvvoooooooooooooooooooorrrrrrrrrrrrrrrrrrrrnnnnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaajjjjjjjjjjjjjjjjjjjjrrrrrrrrrrrrrrrrrrrrwwwwwwwwwwwwwwwwwwwwiiiiiiiiii...

output:

416024000

result:

ok answer is '416024000'

Test #77:

score: 0
Accepted
time: 395ms
memory: 132920kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

151925000000

result:

ok answer is '151925000000'

Test #78:

score: 0
Accepted
time: 367ms
memory: 132916kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

45969000000

result:

ok answer is '45969000000'

Test #79:

score: 0
Accepted
time: 341ms
memory: 145144kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

536440500

result:

ok answer is '536440500'

Test #80:

score: 0
Accepted
time: 287ms
memory: 141080kb

input:

2000 2000
ddddddddddkkkkkkkkkkrrrrrrrrrrwwwwwwwwwwvvvvvvvvvvaaaaaaaaaaoooooooooottttttttttttttttttttzzzzzzzzzzqqqqqqqqqqssssssssssuuuuuuuuuuuuuuuuuuuuxxxxxxxxxxnnnnnnnnnnuuuuuuuuuuzzzzzzzzzzeeeeeeeeeeuuuuuuuuuubbbbbbbbbbnnnnnnnnnnmmmmmmmmmmccccccccccppppppppppnnnnnnnnnnhhhhhhhhhhllllllllllgggggggggg...

output:

95748500

result:

ok answer is '95748500'

Test #81:

score: 0
Accepted
time: 372ms
memory: 138972kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

49867000000

result:

ok answer is '49867000000'

Test #82:

score: 0
Accepted
time: 345ms
memory: 141100kb

input:

2000 2000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

10989000000

result:

ok answer is '10989000000'

Test #83:

score: 0
Accepted
time: 422ms
memory: 134956kb

input:

2000 2000
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

998001000000

result:

ok answer is '998001000000'

Test #84:

score: 0
Accepted
time: 417ms
memory: 132916kb

input:

2000 2000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

249001000000

result:

ok answer is '249001000000'

Test #85:

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

input:

1 1
b

output:

0

result:

ok answer is '0'

Test #86:

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

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

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

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

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: 0ms
memory: 14056kb

input:

1 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #91:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #92:

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

input:

1 2000
bbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #93:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #94:

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

input:

1 2000
bbaaabbbabbbbabbbbbbbaaaabbabbbababbbbabaaaaababbabbbbbaabbbaababbabbbaaabaaabaabbabbababbbabbbbbbaabbbbbaaabbbaabababaaaaabbbaabbbaabbbaaaabbbbaaaababbbababaabaabbaabbabaaabaaaaababaaaabaaabababbbbbaababbaabaababbaababababbabaaababbaaabbbbabbbbbabbabbbaabbbaaaaaaaaaaabbabbbaaababbaababababba...

output:

0

result:

ok answer is '0'

Test #95:

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

input:

1 2000
ybznxtzkzdspabhllysnjejgxhynartagoluiafvuzylklphybjbgbydzwviwrjqqcocnryvxzhilkcbzljokipgrdvilnghahtznvxlfofzrhzqwotlfgeyaratruepvpnfianhskanisdjwmekyahnaaeagdxtplxxudezjkusekalweqvvkaghkhbewxufzucflhkkwjcfikolebosrreyfdoxwgjlqvtvmmbykpzlelzoufjtskvkhilfuesudaugjalzhsjmnxhauphiglkrfpigxueotfds...

output:

0

result:

ok answer is '0'

Test #96:

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

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

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'