QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#360524#1088. Border Similarity UndertakingSolitaryDream#AC ✓3436ms287652kbC++173.3kb2024-03-21 21:01:012024-03-21 21:01:02

Judging History

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

  • [2024-03-21 21:01:02]
  • 评测
  • 测评结果:AC
  • 用时:3436ms
  • 内存:287652kb
  • [2024-03-21 21:01:01]
  • 提交

answer

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

#define int long long

const int N=2e3+1e2+7;

int n,m;

string s[N];

void trans(vector<vector<int> >&a,int &n,int &m)
{
    vector<vector<int> >b(m+2,vector<int>(n+2));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            b[i][j]=a[j][i];
    swap(n,m);
    a.swap(b);
}

int ans;

int u[N][N],l[N][N],d[N][N],r[N][N];

int cl[N][N],cr[N][N];

void solve(vector<vector<int> >&a,int n,int m)
{
    if(n>m)
        trans(a,n,m);
    if(n==1)
        return;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            l[i][j]=a[i][j]==a[i][j-1]?l[i][j-1]+1:1,u[i][j]=a[i][j]==a[i-1][j]?u[i-1][j]+1:1;
    for(int i=n;i>=1;i--)
        for(int j=m;j>=1;j--)
            d[i][j]=a[i][j]==a[i+1][j]?d[i+1][j]+1:1,r[i][j]=a[i][j]==a[i][j+1]?r[i][j+1]+1:1;
    int mid=(m+1)>>1;
    for(int i=1;i<=n;i++)
    {
        {
            vector<int> s(n+1);
            for(int k=mid-l[i][mid]+1;k<=mid;k++)
                s[u[i][k]]++;
            for(int i=n-1;i>=1;i--)
                s[i]+=s[i+1];
            for(int j=1;j<i;j++)
            {
                if(l[j][mid]>l[i][mid])
                    cl[j][i]+=s[i-j];
            }
        }
        {
            vector<int> s(n+1);
            for(int k=mid-l[i][mid]+1;k<=mid;k++)
                s[d[i][k]]++;
            for(int i=n-1;i>=1;i--)
                s[i]+=s[i+1];
            for(int j=i+1;j<=n;j++)
            {
                if(l[j][mid]>=l[i][mid])
                    cl[i][j]+=s[j-i];
            }
        }
    }

    
    for(int i=1;i<=n;i++)
    {
        {
            vector<int> s(n+1);
            for(int k=mid+1;k<=r[i][mid+1]+mid;k++)
                s[u[i][k]]++;
            for(int i=n-1;i>=1;i--)
                s[i]+=s[i+1];
            for(int j=1;j<i;j++)
            {
                if(r[j][mid+1]>r[i][mid+1])
                    cr[j][i]+=s[i-j];
            }
        }
        {
            vector<int> s(n+1);
            for(int k=mid+1;k<=r[i][mid+1]+mid;k++)
                s[d[i][k]]++;
            for(int i=n-1;i>=1;i--)
                s[i]+=s[i+1];
            for(int j=i+1;j<=n;j++)
            {
                if(r[j][mid+1]>=r[i][mid+1])
                    cr[i][j]+=s[j-i];
            }
        }
    }

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(a[i][mid]==a[i][mid+1]&&a[i][mid]==a[j][mid]&&a[i][mid+1]==a[j][mid+1])
                ans+=cl[i][j]*cr[i][j];
            cl[i][j]=cr[i][j]=0;
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            u[i][j]=l[i][j]=r[i][j]=d[i][j]=0;
    vector<vector<int> >al(n+2,vector<int>(mid+2));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=mid;j++)
            al[i][j]=a[i][j];
    solve(al,n,mid);
    vector<vector<int> >ar(n+2,vector<int>((m-mid)+2));
    
    for(int i=1;i<=n;i++)
        for(int j=mid+1;j<=m;j++)
            ar[i][j-mid]=a[i][j];
    solve(ar,n,m-mid);
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>s[i],s[i]=' '+s[i];
    vector<vector<int> >a(n+2,vector<int>(m+2));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            a[i][j]=(s[i][j]);
    solve(a,n,m);
    cout<<ans<<"\n";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 5
zzzzz
zxzxz
zzzzz

output:

3

result:

ok answer is '3'

Test #2:

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

input:

4 4
abbc
bcca
babc
acbb

output:

0

result:

ok answer is '0'

Test #3:

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

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

input:

200 200
aabababbaabbaabaaaabbabaaaaabababbbaaabbbbbbaabbbbbababaabbbabaaaabaaababababababbbbbbabababbbbbababbaababbabaabababbbaabbaaaabbababbaabbaaaaaababbbbbbbbabababbbbababbaaaabbabaaaabaaaababaababaabaabaa
bbabababaabbaaabaaaaabbabbbbbbaabaababaaaabaaaaabbbbbababbaaabbaaabbbaaaabaabbbabbabbaababa...

output:

9063

result:

ok answer is '9063'

Test #5:

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

input:

200 200
bbcacaacbcabaacacbacabcccbbacbbbabaccbcabacbacaccbabcbcbaaacbacbaccbbacabbabbbbaccabcacbccaaaaaabacbcabcacbcacbbcbcbbababcccabccaaacabcbccbcbacccbbbcacacbcbbaccaabcbcababbccbcbacbcaaaacabaccaabacabbca
abbbbaacabcbabacaabcccbbcabaabcaacacacacbabbccbabbcbbcbacbbaababbcbbcacbbbabcbbcbbbbabaaaab...

output:

1993

result:

ok answer is '1993'

Test #6:

score: 0
Accepted
time: 21ms
memory: 31268kb

input:

200 200
daadbcdabdabbcbabacdbdaaabbbdbcbbcdaacababcbbdcdbadbadbbccdcbdbbabbddadaccaaaddacdaddaadaaacbdacbcacbdbcaaddddadcdacaaaaccdaadadaaabadbbdcbcbadccbcabccddaddbcdadbdcddcdbaabaacccdaddcdddcaccbddcdaddcbc
adadabcbbacacdadbbaadbbacaccccaabcadbccdddcdbaabacdcaaccbddaadcbcaadcccdbcdccdacbbbbcbabdcb...

output:

725

result:

ok answer is '725'

Test #7:

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

input:

200 200
txxwjvdrstzdlvxbapbangqherrnvedtncukdffoafsxdpbjhowrytghnpxjdylejgnxmvagxqkgrmektefspdsfzyshkavoputrpszynegndfaxqwuexqhsoqqixyakpshebggckjonwsjaiffhgpimqblmjymlltdanrmkgfpvmuzdntucrrtverpfdeellblawwyk
jieyodnvjkcmuomidegwcrinowmvivwnqvwwffmmhxjktznptunvuxcxanknhevtgchvotjifeutehgbsemomcvtahx...

output:

4

result:

ok answer is '4'

Test #8:

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

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

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

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

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

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

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

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

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

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

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

input:

200 200
bbbbbbbbaabbaabbbbabbbbbbbbbabbbababbbbbbbbbbbbbbbbabbbabbbbbbabbbbabaaabbbbbbbbbbbbaabbaababbabbbabbbbbbababaabbbbbabbbaabaabbbbbabbabbababbbbbbbaabaababbbababbbbbababbababbbbbbbaababababbbbbabbabbbb
bbbbbbbbbbbbbabbbbbbabaabbaabababbaaaaaabbbbbabbbbabbbbabbbbbabbbbbbababbbbbbbbaabbbbabaaba...

output:

65918

result:

ok answer is '65918'

Test #19:

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

input:

200 200
bbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbabbbbbbbbbabbbbbbabbbbbbbabbbbbbbbbbbbbabbbabbbbbbbbbabbbbbbbabbbabbbbbbbbbbabbbabbbbbbbbbbbbbbaababbbbbbbbbbabbbbaabbbbabbbbbbbbbbbabbbbbbbbbbabbbabbbbabbbbbb
bbbbabbbbbbbbbbbbbbabbbbababbbabbbbbabbbbbbbbbababbabbbbbbbbbbbbababbbbbbbbabbbaaababbbbbbb...

output:

436980

result:

ok answer is '436980'

Test #20:

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

input:

200 200
bbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbabbbbbbbbbbbbbabbbbbbbabbbbab
bbbbbbbbbbabbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbbbbabbbabbab...

output:

2006888

result:

ok answer is '2006888'

Test #21:

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

input:

200 200
bbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbbbbbbbb...

output:

8811371

result:

ok answer is '8811371'

Test #22:

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

input:

200 200
bbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbabbbbbbbbbbbabbbbbbbbbbabbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbb...

output:

29949725

result:

ok answer is '29949725'

Test #23:

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

input:

200 200
aabaaaaaaaabaaaaaabaaaaabaaabaaaababaabaabbaabaaaaaaaaaabaaaaaaabaaaaaababaaabbabaaababaababaaaaaaaaaaaabaaaaabaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaababbaaaaaaaaaaaaaaabaaabaabbbbabaaaaaaaaaaaaabaaa
aaaaaaaabbaaaaaaaabbaaaaaabaabbaaaabaaaabbabaaaabaaaaaabaaaaabbbaaaabaaabaaabbababbabbaabaa...

output:

62746

result:

ok answer is '62746'

Test #24:

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

input:

200 200
aabaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaaaaaaaababaabaabaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaabaaabaaaaaaaabaaaaaabaaaaaaaaaaaaaaabaabaaaabaaaaaaaaabaaabaaaaaaaaaaaabaaaaaabbaaaabaaaa
aabaaaaabaabaaaaaaababaaabaaaaaaabaaaaaaaaaaaaaaaaabbabaaaaaaaaaaaaaaaaaaaaaaababaabbaabaab...

output:

393455

result:

ok answer is '393455'

Test #25:

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

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaababaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaa...

output:

1744602

result:

ok answer is '1744602'

Test #26:

score: 0
Accepted
time: 21ms
memory: 27108kb

input:

200 200
aaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaa...

output:

7733272

result:

ok answer is '7733272'

Test #27:

score: 0
Accepted
time: 21ms
memory: 31244kb

input:

200 200
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaa...

output:

26388726

result:

ok answer is '26388726'

Test #28:

score: 0
Accepted
time: 2119ms
memory: 285716kb

input:

2000 2000
hxbcuprmlgnupldnbzhcpesdlawilpqilczdvavjoetwdjtjkcdccftawgagfjhfcnkejypkgwswgiibgfxzzcgjdqjmamdkttedmffqievedyicgurwmungupmvuwralxutfnrykylbqrbqquvrchuuoebfapvgsjgasdfnkxrjnflizeqychfhuetijdnuoenucqkktzkurqcpusbncvilxziylxxyprsqwcdrgcviobiapvuxvhignilpavhjuebiwhatxtqvemtmxwlufvdkmqstjpqvos...

output:

238

result:

ok answer is '238'

Test #29:

score: 0
Accepted
time: 3436ms
memory: 287648kb

input:

2000 2000
aabbbabababbbbbbbaabbaabbbbabbaabbbbbbbbabbaabbabaababababbbbbbabaaabbbbbabbaabbaabbaaaabaaabaaaaaabbbbaaaaabbbbabbaaaababbaaaabbaabaababaaaabaaaaaabbbaabaabbbbbabaaaaaaabaaabbaabaababaaabbbaababababaabbbbbaabbbaabaaabbbbaababaaabaaabbaabaaaaaababbabbaaabbbababaabaabaabbbaabaabbbbbaaababbb...

output:

888377

result:

ok answer is '888377'

Test #30:

score: 0
Accepted
time: 157ms
memory: 26080kb

input:

100 2000
baaabbabbaaababaaababbbabbabaaaabbbbbbbbabababbaabaabaaaaaaaabbbbbaaaaaaaaaabaabbbaabaabaaabaaaababbbbbaaaaabbbaaabbbaababbaaaaabbabaaaaaaaabaabaabbbbbbbbbaaabaababbaaabbbaabbaaaaaaabbbabaaabbabbbaaaabbabbababbaaaabbabbaaaaaababbbbababaabbabbabbbbbabbaababbabbbaabbbaabbababbbabbabbaaabbbbbb...

output:

44364

result:

ok answer is '44364'

Test #31:

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

input:

3 2000
abaabbbbaaabbbaaaababaaaabbbbaaaaabaabbaaaabbaaaaabababaababababbbabbbabbbabbbbbabaaabaabaabbaaabaaabbabbaabbabbbbabaabbabbbaabbbbbabbabbbababaaaabaabaabaaaabaabaabaaaaabbababbbbbaabbabbaababbbaaababaaaaaaababbbabbaabbabbbababaababababbabbbababbbaabbabaaaabbaabaaaabbaabbabaabaababbababbbabaab...

output:

771

result:

ok answer is '771'

Test #32:

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

input:

2 2000
aabaabaaabbbbaababbaaabbabaaaaabaaabbbabababaaaaabaabbaababaaabbaaaabaabaababbabbbbaaabbbbbaabaaaabbaababbaabaaabbbbbbaaaaabababbaaaababbbabbbbaabbbbaabaaaaaaaaaaabbbabaaaaaabababaaaaabbaaababaabababababaabbbabaababbbabbaaaaabbabbaaaaaabbbbaabaaabbaabaaabbbbbaabaaabaaaaaabbaababbaaaaabbabbbba...

output:

309

result:

ok answer is '309'

Test #33:

score: 0
Accepted
time: 3188ms
memory: 287580kb

input:

2000 2000
bbbbbbbbbababbbbbbbbbbabbabbbbbbbabbbbbbbbbababaaabbaabbbbaabbaababbbaabaabbabbbbbaaababbbabbabbbbbbabbbbbababbabbabababaabbbbabbbbabbabbbabbbabbbbabbbbabbabaaabbbbaabaababbbbbbaabaabbbbabbbbaaabbbbbaabbabbaabababaabbbbbbbbbbababaababbbbbbbbbbababaabbbaabbbbbbbbbbbbbabbbaaabaabbbbbabbbabbb...

output:

6611891

result:

ok answer is '6611891'

Test #34:

score: 0
Accepted
time: 2793ms
memory: 285604kb

input:

2000 2000
bbabbbbbabbbbbbbababbabbbbbbbbabbbbbbabbabbbababbbbbbbbbbbbbabbbbbbbbbbbbabbbababbbbbbbbbbbbbbbbbbbabbbbabbbbabbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbabbbbbbabbbbbbbbbbabaababaabbbbbbbbbbbbbbbbbbabbbbabbbabbbbbbbbbbbbbbbabbbbbbbbbbbbbbbabbbabbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

42485356

result:

ok answer is '42485356'

Test #35:

score: 0
Accepted
time: 2525ms
memory: 285392kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbabbbbbabbbbbbaabbabbbbbabbbbbbbbbbbbbbbbbbbaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbabbbbb...

output:

208474291

result:

ok answer is '208474291'

Test #36:

score: 0
Accepted
time: 2371ms
memory: 287392kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbababbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

920144952

result:

ok answer is '920144952'

Test #37:

score: 0
Accepted
time: 2297ms
memory: 287280kb

input:

2000 2000
bbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3800182739

result:

ok answer is '3800182739'

Test #38:

score: 0
Accepted
time: 3189ms
memory: 287648kb

input:

2000 2000
aaaabbabbabaaaaabaaaaabbaaaabaabaabaaaaaaaaaaaabaababaaabbaabaababaaaaaaabaabaaabbbabaaaaabaaaabaaaaaaaaaaaaabaaaaaaaabbaaaabaaaaaaaaaabbbaabaabaaaaaabaaaaabbaaaaababaaaaaabbaaaaaaabaaaaaabaaaaabbbaaaaaaaaabbbababaaaaaaaaaabaaaaaaaaaaaaaababababaaaaaaaabbaaabaaabbaabbaaaaababaaaaaabaaaabaa...

output:

6633997

result:

ok answer is '6633997'

Test #39:

score: 0
Accepted
time: 2773ms
memory: 287360kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaabaaaabaaaaababbaaaabaaaababaaaaaaabaaaaaaaaaaaaaabaaabaaaaaabaaaaaaaaaaaabbaaabaaaaababaababaaaaabababaaaaabaaaaaaaaaaabaabbaaaabaaaaaaaabaaaaaaaaaaaaaaaabbaaaaaaaabaaaaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaabaaaaaaabaaaaaaaaaabaaaaaaaaabbabaaaaababaabaabaaaaaaaa...

output:

42677036

result:

ok answer is '42677036'

Test #40:

score: 0
Accepted
time: 2546ms
memory: 287652kb

input:

2000 2000
aaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaabaaabaaaaabaaaaaaaaaaaaaabaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaabaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaa...

output:

209624629

result:

ok answer is '209624629'

Test #41:

score: 0
Accepted
time: 2378ms
memory: 285600kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaba...

output:

908496629

result:

ok answer is '908496629'

Test #42:

score: 0
Accepted
time: 2333ms
memory: 287652kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3819264516

result:

ok answer is '3819264516'

Test #43:

score: 0
Accepted
time: 2241ms
memory: 287416kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2193746696652

result:

ok answer is '2193746696652'

Test #44:

score: 0
Accepted
time: 2235ms
memory: 287648kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

2886592675758

result:

ok answer is '2886592675758'

Test #45:

score: 0
Accepted
time: 2204ms
memory: 287420kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3460768674956

result:

ok answer is '3460768674956'

Test #46:

score: 0
Accepted
time: 2199ms
memory: 285304kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3680478183757

result:

ok answer is '3680478183757'

Test #47:

score: 0
Accepted
time: 2224ms
memory: 287452kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3834982314152

result:

ok answer is '3834982314152'

Test #48:

score: 0
Accepted
time: 2210ms
memory: 287644kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2113716926482

result:

ok answer is '2113716926482'

Test #49:

score: 0
Accepted
time: 2210ms
memory: 287616kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2884992951736

result:

ok answer is '2884992951736'

Test #50:

score: 0
Accepted
time: 2243ms
memory: 287652kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3434267490537

result:

ok answer is '3434267490537'

Test #51:

score: 0
Accepted
time: 2204ms
memory: 287448kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3693371002932

result:

ok answer is '3693371002932'

Test #52:

score: 0
Accepted
time: 2223ms
memory: 285248kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3833465918348

result:

ok answer is '3833465918348'

Test #53:

score: 0
Accepted
time: 2202ms
memory: 287304kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #54:

score: 0
Accepted
time: 2220ms
memory: 287616kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

3996001000000

result:

ok answer is '3996001000000'

Test #55:

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

input:

20 2000
bbbbbabbbabbbbbabbbbbbbbaaaabaabbaabbbbaabbbabbabbabbaabbbabbabbabbbbbbaabbbbbababbabbbbbbabbbbbbbbbbbaabbabbbbbaababbbbbbbbabbbabbbbbbbabbbbbbbbbabbbabbabbbbaababbbbbbbbaabbbabbbbbbbbbabbbaabbbaabbbbbababbbbbbbbabbbbbbbabbbbbbbbabbbbbababbbbbbbbbbbbbbbbababbbbbbbbbbbaaabbabbbbabbbbbaabbbbab...

output:

56816

result:

ok answer is '56816'

Test #56:

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

input:

20 2000
bbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbababbabbabbabbbbabbbbbbabbbabbbbbabbbbabbbbbabbbbbbabbbbbbbbbbbbaabbabbbbababbbabbbbbbbbbbabbbabbbbbbbbbbbbbbbaabbabbbbbbbbbbbbbbabbbbabbabbbbbbbabbabbbbbbbbbbbabbbbabbbaabbaaabbbbbbbabbbbbbbbbbbbbabbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbabbbb...

output:

355419

result:

ok answer is '355419'

Test #57:

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

input:

20 2000
abbbbbabbbabbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbababbbbbbbbabbabbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbabbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbabbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbaabbbbbb...

output:

1290507

result:

ok answer is '1290507'

Test #58:

score: 0
Accepted
time: 15ms
memory: 19324kb

input:

20 2000
abbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbb...

output:

3673870

result:

ok answer is '3673870'

Test #59:

score: 0
Accepted
time: 16ms
memory: 13420kb

input:

20 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

9771068

result:

ok answer is '9771068'

Test #60:

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

input:

20 2000
babaabaaaababaaabaaaaaaaaaaaabaaaabaaaaaabbaababaababaaaaaaaaaaaaaabaaaaaaaabaaaaaabbaaaaaaababaaaaaaabaaabaaaababaaaabaaaabbbababaaaaaababaaababaaaaaaaabaaaaaaabaaababaaabaaaaaaababaabaaaaaabaaaaaaaaaaaabaaaaaaaaabaabbaaaababaaaaaabaaaababaaaaabaabbabaaabbaaaabaaaaababababaabaabaaaaabaabaaa...

output:

57804

result:

ok answer is '57804'

Test #61:

score: 0
Accepted
time: 21ms
memory: 15468kb

input:

20 2000
aaaaaaaaaaabaaabaaabaaaaabbbaaaaaaaabaaaaaaaabaabaaaaaabaaaaabababbaaaaaabaaaaaaabbabaaaaaaaaaaaaaabaaaaaaababaaaaaabaaaaaaaaaaaaaabaaaaaaaaaaaabaaaaaaaaaaaababaaaaaaaaaaaaaaaabaaaabaaaaaaaaaaaabaaaaaaabaaabaaabaaabaabaaabaaaaaaabbaaaaabaabaaaabaabaaabaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaa...

output:

361169

result:

ok answer is '361169'

Test #62:

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

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaabaaaaaaaaaabaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaababaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaabaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaabaaaaaaaaaaaaaaaaaa...

output:

1287432

result:

ok answer is '1287432'

Test #63:

score: 0
Accepted
time: 21ms
memory: 13120kb

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaabaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaba...

output:

3785925

result:

ok answer is '3785925'

Test #64:

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

input:

20 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

9744215

result:

ok answer is '9744215'

Test #65:

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

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

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

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

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

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

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

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

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

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

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

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaa...

output:

2191400000

result:

ok answer is '2191400000'

Test #76:

score: 0
Accepted
time: 2078ms
memory: 285564kb

input:

2000 2000
ccccccccccccccccccccaaaaaaaaaaaaaaaaaaaavvvvvvvvvvvvvvvvvvvvppppppppppppppppppppvvvvvvvvvvvvvvvvvvvvttttttttttttttttttttvvvvvvvvvvvvvvvvvvvvoooooooooooooooooooorrrrrrrrrrrrrrrrrrrrnnnnnnnnnnnnnnnnnnnnaaaaaaaaaaaaaaaaaaaajjjjjjjjjjjjjjjjjjjjrrrrrrrrrrrrrrrrrrrrwwwwwwwwwwwwwwwwwwwwiiiiiiiiii...

output:

416024000

result:

ok answer is '416024000'

Test #77:

score: 0
Accepted
time: 2185ms
memory: 285480kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

151925000000

result:

ok answer is '151925000000'

Test #78:

score: 0
Accepted
time: 2116ms
memory: 287452kb

input:

2000 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

45969000000

result:

ok answer is '45969000000'

Test #79:

score: 0
Accepted
time: 2186ms
memory: 285596kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

536440500

result:

ok answer is '536440500'

Test #80:

score: 0
Accepted
time: 2077ms
memory: 287612kb

input:

2000 2000
ddddddddddkkkkkkkkkkrrrrrrrrrrwwwwwwwwwwvvvvvvvvvvaaaaaaaaaaoooooooooottttttttttttttttttttzzzzzzzzzzqqqqqqqqqqssssssssssuuuuuuuuuuuuuuuuuuuuxxxxxxxxxxnnnnnnnnnnuuuuuuuuuuzzzzzzzzzzeeeeeeeeeeuuuuuuuuuubbbbbbbbbbnnnnnnnnnnmmmmmmmmmmccccccccccppppppppppnnnnnnnnnnhhhhhhhhhhllllllllllgggggggggg...

output:

95748500

result:

ok answer is '95748500'

Test #81:

score: 0
Accepted
time: 2175ms
memory: 287452kb

input:

2000 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

49867000000

result:

ok answer is '49867000000'

Test #82:

score: 0
Accepted
time: 2109ms
memory: 287452kb

input:

2000 2000
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr...

output:

10989000000

result:

ok answer is '10989000000'

Test #83:

score: 0
Accepted
time: 2230ms
memory: 285368kb

input:

2000 2000
uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

998001000000

result:

ok answer is '998001000000'

Test #84:

score: 0
Accepted
time: 2201ms
memory: 287356kb

input:

2000 2000
gggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggg...

output:

249001000000

result:

ok answer is '249001000000'

Test #85:

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

input:

1 1
b

output:

0

result:

ok answer is '0'

Test #86:

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

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

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

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

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

input:

1 2000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #91:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #92:

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

input:

1 2000
bbbbbbbbbabbbbbbbbbabbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbabbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

0

result:

ok answer is '0'

Test #93:

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

input:

1 2000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Test #94:

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

input:

1 2000
bbaaabbbabbbbabbbbbbbaaaabbabbbababbbbabaaaaababbabbbbbaabbbaababbabbbaaabaaabaabbabbababbbabbbbbbaabbbbbaaabbbaabababaaaaabbbaabbbaabbbaaaabbbbaaaababbbababaabaabbaabbabaaabaaaaababaaaabaaabababbbbbaababbaabaababbaababababbabaaababbaaabbbbabbbbbabbabbbaabbbaaaaaaaaaaabbabbbaaababbaababababba...

output:

0

result:

ok answer is '0'

Test #95:

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

input:

1 2000
ybznxtzkzdspabhllysnjejgxhynartagoluiafvuzylklphybjbgbydzwviwrjqqcocnryvxzhilkcbzljokipgrdvilnghahtznvxlfofzrhzqwotlfgeyaratruepvpnfianhskanisdjwmekyahnaaeagdxtplxxudezjkusekalweqvvkaghkhbewxufzucflhkkwjcfikolebosrreyfdoxwgjlqvtvmmbykpzlelzoufjtskvkhilfuesudaugjalzhsjmnxhauphiglkrfpigxueotfds...

output:

0

result:

ok answer is '0'

Test #96:

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

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

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'