QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#267308#5256. InsertionsleexzqAC ✓16ms27380kbC++143.6kb2023-11-27 07:30:372023-11-27 07:30:38

Judging History

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

  • [2023-11-27 07:30:38]
  • 评测
  • 测评结果:AC
  • 用时:16ms
  • 内存:27380kb
  • [2023-11-27 07:30:37]
  • 提交

answer

//I play to win
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
const int N=1e5+10;
struct BIT
{
    int c[N];
    void add(int l,int r,int v){Add(l,v),Add(r+1,-v);}
    void Add(int x,int v){for(;x<N;x+=x&-x)c[x]+=v;}
    int ask(int x){int r=0;for(;x;x&=x-1)r+=c[x];return r;}
}T;
char s[N],t[N],p[N],rs[N],rt[N],rp[N];
int nxtp[N],nxtrp[N],nxtt[N],nxtrt[N];
int n,m,k,ans[N],ansc[N];
void get_nxt(char *s,int *nxt)
{
    nxt[0]=-1;
    for(int i=2,j=0;s[i];i++)
    {
        while(~j&&s[j+1]!=s[i])j=nxt[j];
        nxt[i]=++j;
    }
}
vector<int>getq(char *s,char *t,int *nxt,int sz)
{
    int j=0;
    vector<int>q;
    for(int i=1;s[i];i++,j++)
        while(~j&&t[j+1]!=s[i])j=nxt[j];
    if(j==sz)j=nxt[j];
    while(j)q.push_back(sz-j),j=nxt[j];
    return q;
}
int c[N];
void solve(char *s,char *t,int*nxt,vector<int>&q)
{
    memset(c,0,sizeof c);
    for(int x:q)c[x]++;
    for(int i=1;t[i];i++)c[i]+=c[nxt[i]];
    memset(ansc,0,sizeof ansc);
    for(int i=1,j=0;s[i];i++)
    {
        while(~j&&s[i]!=t[j+1])j=nxt[j];
        ansc[i]=c[++j];
    }
}
vector<int>v[N];
vector<array<int,3>>M[N];
vector<pi>Q[N];
int bg1[N],ed1[N],bg2[N],ed2[N],cnt,pos1[N],pos2[N];
void dfs(int x,int *bg,int* ed)
{bg[x]=++cnt;for(int y:v[x])dfs(y,bg,ed);ed[x]=cnt;}
void buildT(int*nxt,int sz)
{v[0].clear();for(int i=1;i<=sz;i++)v[i].clear(),v[nxt[i]].push_back(i);}
void getpos(char *s,char *t,int *nxt,int *pos)
{
    for(int i=1,j=0;s[i];i++)
    {
        while(~j&&s[i]!=t[j+1])j=nxt[j];
        pos[i]=++j;
    }
}
void match(char*s,char*t,int*nxt)
{
    memset(ansc,0,sizeof ansc);
    for(int i=1,j=0;s[i];i++)
    {
        while(~j&&s[i]!=t[j+1])j=nxt[j];
        if(!t[++j+1])j=nxt[j],ansc[i]++;
        ansc[i]+=ansc[i-1];
    }
}
int main()
{
    scanf("%s%s%s",s+1,t+1,p+1);
    n=strlen(s+1),m=strlen(t+1),k=strlen(p+1);
    memcpy(rs,s,N),memcpy(rt,t,N),memcpy(rp,p,N);
    reverse(rs+1,rs+n+1),reverse(rt+1,rt+m+1),reverse(rp+1,rp+k+1);
    get_nxt(p,nxtp),get_nxt(rp,nxtrp),get_nxt(t,nxtt),get_nxt(rt,nxtrt);
    match(s,p,nxtp);
    for(int i=1;i<=n;i++)ans[i]+=ansc[i];
    match(rs,rp,nxtrp);
    for(int i=1;i<=n;i++)ans[n-i]+=ansc[i];
    vector<int>q;
    q=getq(p,t,nxtt,k);
    solve(s,p,nxtp,q);
    for(int i=1;i<=n;i++)ans[i]+=ansc[i];
    q=getq(rp,rt,nxtrt,k);
    solve(rs,rp,nxtrp,q);
    for(int i=1;i<=n;i++)ans[n-i]+=ansc[i];
    if(m<k)
    {
        q.clear();
        for(int i=2,j=0;i<k;i++)
        {
            while(~j&&t[j+1]!=p[i])j=nxtt[j];
            if(++j==m)j=nxtt[j],q.push_back(i);
        }
        buildT(nxtp,k),cnt=0,dfs(0,bg1,ed1);
        buildT(nxtrp,k),cnt=0,dfs(0,bg2,ed2);
        for(int x:q)
        {
            int l1=bg1[x-m],r1=ed1[x-m],l2=bg2[k-x],r2=ed2[k-x];
            M[l1].push_back({l2,r2,1});
            M[r1+1].push_back({l2,r2,-1});
        }
        getpos(s,p,nxtp,pos1);
        getpos(rs,rp,nxtrp,pos2);
        for(int i=1;i<n;i++)
            Q[bg1[pos1[i]]].push_back({bg2[pos2[n-i]],i});
        for(int i=1;i<=k+1;i++)
        {
            for(auto[l,r,v]:M[i])T.add(l,r,v);
            for(auto[p,id]:Q[i])ans[id]+=T.ask(p);
        }
    }
    else 
    {
        match(t,p,nxtp);
        for(int i=0;i<=n;i++)ans[i]+=ansc[m];
    }
    int mx=0,c=0,lp=0,rp=0;
    for(int i=0;i<=n;i++)
        if(ans[i]>mx)mx=ans[i],c=1,lp=rp=i;
        else if(ans[i]==mx)c++,rp=i;
    cout<<mx<<" "<<c<<" "<<lp<<" "<<rp<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

ok 4 number(s): "2 2 6 7"

Test #2:

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

input:

z
zzkkzzkk
z

output:

5 2 0 1

result:

ok 4 number(s): "5 2 0 1"

Test #3:

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

input:

wgwwggggw
g
gggg

output:

2 5 4 8

result:

ok 4 number(s): "2 5 4 8"

Test #4:

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

input:

q
uuquu
u

output:

4 2 0 1

result:

ok 4 number(s): "4 2 0 1"

Test #5:

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

input:

gpgggpppg
pg
gpgg

output:

2 1 4 4

result:

ok 4 number(s): "2 1 4 4"

Test #6:

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

input:

p
xpxp
p

output:

3 2 0 1

result:

ok 4 number(s): "3 2 0 1"

Test #7:

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

input:

aacaacacaa
ca
caca

output:

2 5 2 9

result:

ok 4 number(s): "2 5 2 9"

Test #8:

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

input:

k
kekekkekk
k

output:

7 2 0 1

result:

ok 4 number(s): "7 2 0 1"

Test #9:

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

input:

ghhhhg
g
ghhg

output:

2 1 3 3

result:

ok 4 number(s): "2 1 3 3"

Test #10:

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

input:

b
xbb
b

output:

3 2 0 1

result:

ok 4 number(s): "3 2 0 1"

Test #11:

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

input:

nddnnndndn
dnd
ndndn

output:

3 1 5 5

result:

ok 4 number(s): "3 1 5 5"

Test #12:

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

input:

imiimmmm
miimi
i

output:

6 9 0 8

result:

ok 4 number(s): "6 9 0 8"

Test #13:

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

input:

gzzzzzzzzz
zgzzzg
gzgggzzz

output:

0 11 0 10

result:

ok 4 number(s): "0 11 0 10"

Test #14:

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

input:

m
mmwmwmw
wwmww

output:

0 2 0 1

result:

ok 4 number(s): "0 2 0 1"

Test #15:

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

input:

jmmmmjmmj
jmjjjmjm
mjmmmmjj

output:

0 10 0 9

result:

ok 4 number(s): "0 10 0 9"

Test #16:

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

input:

f
ffffwff
wffw

output:

0 2 0 1

result:

ok 4 number(s): "0 2 0 1"

Test #17:

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

input:

plpll
llplll
pppppppl

output:

0 6 0 5

result:

ok 4 number(s): "0 6 0 5"

Test #18:

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

input:

yypppypyy
ppyyypppy
ypyppypp

output:

0 10 0 9

result:

ok 4 number(s): "0 10 0 9"

Test #19:

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

input:

okkkkkok
okokkkoo
kookooko

output:

0 9 0 8

result:

ok 4 number(s): "0 9 0 8"

Test #20:

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

input:

ccc
cpppp
cc

output:

3 1 3 3

result:

ok 4 number(s): "3 1 3 3"

Test #21:

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

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

631 1000 0 999

result:

ok 4 number(s): "631 1000 0 999"

Test #22:

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

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #23:

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

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:

0 1000 0 999

result:

ok 4 number(s): "0 1000 0 999"

Test #24:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 413 587 999

result:

ok 4 number(s): "1 413 587 999"

Test #25:

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

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:

315 2 1 998

result:

ok 4 number(s): "315 2 1 998"

Test #26:

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

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:

260 1 113 113

result:

ok 4 number(s): "260 1 113 113"

Test #27:

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

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

748 907 0 906

result:

ok 4 number(s): "748 907 0 906"

Test #28:

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

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #29:

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

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:

0 907 0 906

result:

ok 4 number(s): "0 907 0 906"

Test #30:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1 702 0 701

result:

ok 4 number(s): "1 702 0 701"

Test #31:

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

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:

374 454 0 906

result:

ok 4 number(s): "374 454 0 906"

Test #32:

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

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:

291 370 50 788

result:

ok 4 number(s): "291 370 50 788"

Test #33:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

937 966 0 965

result:

ok 4 number(s): "937 966 0 965"

Test #34:

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

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:

35 64 600 663

result:

ok 4 number(s): "35 64 600 663"

Test #35:

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

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:

0 966 0 965

result:

ok 4 number(s): "0 966 0 965"

Test #36:

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

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

1 768 0 767

result:

ok 4 number(s): "1 768 0 767"

Test #37:

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

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:

468 483 0 964

result:

ok 4 number(s): "468 483 0 964"

Test #38:

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

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:

429 443 80 964

result:

ok 4 number(s): "429 443 80 964"

Test #39:

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

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

44459 99774 0 99773

result:

ok 4 number(s): "44459 99774 0 99773"

Test #40:

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

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #41:

score: 0
Accepted
time: 11ms
memory: 17716kb

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:

0 99774 0 99773

result:

ok 4 number(s): "0 99774 0 99773"

Test #42:

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

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 61041 38733 99773

result:

ok 4 number(s): "1 61041 38733 99773"

Test #43:

score: 0
Accepted
time: 11ms
memory: 24636kb

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #44:

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

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:

22229 2 1 99772

result:

ok 4 number(s): "22229 2 1 99772"

Test #45:

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

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

85548 90750 0 90749

result:

ok 4 number(s): "85548 90750 0 90749"

Test #46:

score: 0
Accepted
time: 11ms
memory: 22812kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #47:

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

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:

0 90750 0 90749

result:

ok 4 number(s): "0 90750 0 90749"

Test #48:

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

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1 71220 19530 90749

result:

ok 4 number(s): "1 71220 19530 90749"

Test #49:

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

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:

42774 45375 0 90748

result:

ok 4 number(s): "42774 45375 0 90748"

Test #50:

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

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:

40492 43093 2508 88692

result:

ok 4 number(s): "40492 43093 2508 88692"

Test #51:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

97181 91251 0 91250

result:

ok 4 number(s): "97181 91251 0 91250"

Test #52:

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

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

6028 98 22809 22906

result:

ok 4 number(s): "6028 98 22809 22906"

Test #53:

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

input:

qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...

output:

0 91251 0 91250

result:

ok 4 number(s): "0 91251 0 91250"

Test #54:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 4772 86479 91250

result:

ok 4 number(s): "1 4772 86479 91250"

Test #55:

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

input:

lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...

output:

48590 45626 0 91250

result:

ok 4 number(s): "48590 45626 0 91250"

Test #56:

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

input:

ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...

output:

22317 19352 36850 75552

result:

ok 4 number(s): "22317 19352 36850 75552"

Test #57:

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

input:

abbababa
babbba
bbab

output:

2 6 1 7

result:

ok 4 number(s): "2 6 1 7"

Test #58:

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

input:

ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba
aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab
abbbbaabaa

output:

1 7 43 99

result:

ok 4 number(s): "1 7 43 99"