QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#358169#5256. InsertionszaaAC ✓22ms37624kbC++203.9kb2024-03-19 17:56:202024-03-19 17:56:21

Judging History

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

  • [2024-03-19 17:56:21]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:37624kb
  • [2024-03-19 17:56:20]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ls(x) ((x)*2)
#define rs(x) ((x)*2+1)
#define Debug(...) fprintf(stderr, __VA_ARGS__)
#define For(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define Rof(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define rep(i,  b) for(int i=1,i##end=b;i<=i##end;i++)
#define Copy(a,b) memcpy(a,b,sizeof(a))
using namespace std;
const int N=1e6+5,Mod=998244353;
//char buf[(1<<21)+5],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline void chmx(int &x,int y){(x<y)&&(x=y);}
inline void chmn(int &x,int y){(x>y)&&(x=y);}
//inline void Add(int &x,int y){(x=x+y+Mod)%Mod;}
typedef __int128_t i128;
i128 _base=1;
inline int mol(int x){return x-Mod*(_base*x>>64);}
inline int read(){
	int f=0,x=0;
	char ch=getchar();
	while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return f?-x:x;
}
int n,m,k;
int ans[N];
int sum=0;
struct KMP{
	int nxt[N];
	int a[N],v[N];
	int gg[N];
	char s[N],t[N],p[N];
	inline int init(){
		int j=0;
		For(i,2,k){
			while(j&&p[j+1]!=p[i]) j=nxt[j];
			if(p[j+1]==p[i]) j++;
			nxt[i]=j;
		}
		j=0;
		For(i,1,m){
			while (j==k||(j&&p[j+1]!=t[i])) j=nxt[j];
			if(p[j+1]==t[i])j++;
			if(j==k)++sum;
		}
		return j;
	}
	inline void cal(int o){
		For(i,1,k) a[i]=a[nxt[i]]+v[k-i];
		//~ For(i,1,k) cout<<a[i]<<" ";
		cout<<endl;
		int j=0,res=0;
		For(i,0,n){
			while (j==k||(j&&p[j+1]!=s[i])) j=nxt[j];
			if(p[j+1]==s[i])j++;
			if(j==k) ++res;
			gg[i]=j;
			if(o==0)ans[i]+=res+a[j];
			else ans[n-i]+=res+a[j];
		}
		//~ cout<<endl;
	}
}A,B;
char s[N],t[N],p[N];
int tr[N];
int nxt[N];
int dfn[N],ed[N],cnt;
bool vis[N];
vector<int>q1[N],q2[N];
vector<pair<int,int> > e[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y){while(x<=cnt){tr[x]+=y;x+=lowbit(x);}}
inline int qry(int x){int res=0;while(x){res+=tr[x];x-=lowbit(x);}return res;}
void dfs(int x) {
	dfn[x]=++cnt;
	for(auto y:q2[x]) dfs(y);
	ed[x]=cnt;
}
inline void dfs2(int x){
bool flag=0;
	//~ cout<<x<<" ";
	if(x&&vis[x+m]&&k-(x+m)){
		//~ cout<<k-(x+m);
		//~ cout<<dfn[k-(x+m)]<<" "<<ed[k-(x+m)]<<" ";
		add(dfn[k-(x+m)],1);
		add(ed[k-(x+m)]+1,-1);flag=1;
	}
	for(auto E:e[x]) ans[E.second]+=qry(dfn[E.first]);
	for(auto y:q1[x])dfs2(y);
	if(flag){
		add(dfn[k-(x+m)],-1);
		add(ed[k-(x+m)]+1,1);
	}
}
signed main(){
	_base=(_base<<64)/Mod;
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	// ios::sync_with_stdio(false);
	// cin.tie(0); cout.tie(0);
	scanf("%s",s+1); 
	scanf("%s",t+1); 
	scanf("%s",p+1); 
	n=strlen(s+1);m=strlen(t+1);k=strlen(p+1);
	Copy(A.s,s);Copy(A.t,t);Copy(A.p,p);
	reverse(s+1,s+n+1);
	reverse(t+1,t+m+1);
	reverse(p+1,p+k+1);
	Copy(B.s,s);Copy(B.t,t);Copy(B.p,p);
	//~ For(i,1,n) cout<<B.s[i];
	int ii=A.init(),jj=B.init();
	sum/=2;
	if(ii==k) ii=A.nxt[ii];
	while(ii){
		++B.v[ii];
		ii=A.nxt[ii];
	}
	if(jj==k) jj=B.nxt[jj];
	while(jj){
		++A.v[jj];
		jj=B.nxt[jj];
	}
	A.cal(0);B.cal(1);
	if(m<k){//´¦ÀíA+T+B
		int j=0;
		For(i,2,m){
			while(j&&A.t[j+1]!=A.t[i])j=nxt[j];
			if(A.t[j+1]==A.t[i])j++;
			nxt[i]=j;
		}
		j=0;
		For(i,1,k){
			while(j==m||(j&&A.t[j+1]!=A.p[i])) j=nxt[j];
			if(A.t[j+1]==A.p[i])j++;
			if(j==m) vis[i]=1;
		}
		For(i,1,k){
			q1[A.nxt[i]].push_back(i);
			q2[B.nxt[i]].push_back(i);
		}
		dfs(0);
		//~ For(i,0,k) cout<<dfn[i]<<" "<<ed[i]<<endl;
		For(i,0,n){
			int l=A.gg[i],r=B.gg[n-i];
			if(l&&r) e[l].push_back({r,i});
		}
		dfs2(0);
	}
	int l=0,r=0,maxx=0,num=0;
	For(i,0,n){
		if(ans[i]>maxx){
			l=i;r=i;
			maxx=ans[i];
			num=0;
		}
		if(ans[i]==maxx) num++,r=i;
		//~ cout<<ans[i]<<" ";
	}
	//~ if(maxx==0&&!sum) l=r=num=0;
	printf("%lld %lld %lld %lld\n",maxx+sum,num,l,r);
#ifdef LOCAL
    Debug("\nMy Time: %.3lfs\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}

详细

Test #1:

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

input:

rrddrrrdd
ddrrd
rrddrr

output:



2 2 6 7

result:

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

Test #2:

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

input:

z
zzkkzzkk
z

output:



5 2 0 1

result:

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

Test #3:

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

input:

wgwwggggw
g
gggg

output:



2 5 4 8

result:

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

Test #4:

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

input:

q
uuquu
u

output:



4 2 0 1

result:

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

Test #5:

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

input:

gpgggpppg
pg
gpgg

output:



2 1 4 4

result:

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

Test #6:

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

input:

p
xpxp
p

output:



3 2 0 1

result:

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

Test #7:

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

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

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

input:

ghhhhg
g
ghhg

output:



2 1 3 3

result:

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

Test #10:

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

input:

b
xbb
b

output:



3 2 0 1

result:

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

Test #11:

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

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

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

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

input:

m
mmwmwmw
wwmww

output:



0 2 0 1

result:

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

Test #15:

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

input:

jmmmmjmmj
jmjjjmjm
mjmmmmjj

output:



0 10 0 9

result:

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

Test #16:

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

input:

f
ffffwff
wffw

output:



0 2 0 1

result:

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

Test #17:

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

input:

plpll
llplll
pppppppl

output:



0 6 0 5

result:

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

Test #18:

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

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

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

input:

ccc
cpppp
cc

output:



3 1 3 3

result:

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

Test #21:

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

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:



631 1000 0 999

result:

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

Test #22:

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

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:



0 1000 0 999

result:

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

Test #23:

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

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:



0 1000 0 999

result:

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

Test #24:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:



1 413 587 999

result:

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

Test #25:

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

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:



315 2 1 998

result:

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

Test #26:

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

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:



260 1 113 113

result:

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

Test #27:

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

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:



748 907 0 906

result:

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

Test #28:

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

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:



0 907 0 906

result:

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

Test #29:

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

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:



0 907 0 906

result:

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

Test #30:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:



1 702 0 701

result:

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

Test #31:

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

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:



374 454 0 906

result:

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

Test #32:

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

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:



291 370 50 788

result:

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

Test #33:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:



937 966 0 965

result:

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

Test #34:

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

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:



35 64 600 663

result:

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

Test #35:

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

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:



0 966 0 965

result:

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

Test #36:

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

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:



1 768 0 767

result:

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

Test #37:

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

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:



468 483 0 964

result:

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

Test #38:

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

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:



429 443 80 964

result:

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

Test #39:

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

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:



44459 99774 0 99773

result:

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

Test #40:

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

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:



0 99774 0 99773

result:

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

Test #41:

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

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:



0 99774 0 99773

result:

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

Test #42:

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

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:



1 61041 38733 99773

result:

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

Test #43:

score: 0
Accepted
time: 17ms
memory: 35624kb

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:



22229 2 1 99772

result:

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

Test #44:

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

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:



22229 2 1 99772

result:

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

Test #45:

score: 0
Accepted
time: 12ms
memory: 36920kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:



85548 90750 0 90749

result:

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

Test #46:

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

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:



0 90750 0 90749

result:

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

Test #47:

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

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:



0 90750 0 90749

result:

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

Test #48:

score: 0
Accepted
time: 17ms
memory: 29984kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:



1 71220 19530 90749

result:

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

Test #49:

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

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:



42774 45375 0 90748

result:

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

Test #50:

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

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:



40492 43093 2508 88692

result:

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

Test #51:

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

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:



97181 91251 0 91250

result:

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

Test #52:

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

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:



6028 98 22809 22906

result:

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

Test #53:

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

input:

qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...

output:



0 91251 0 91250

result:

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

Test #54:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:



1 4772 86479 91250

result:

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

Test #55:

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

input:

lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...

output:



48590 45626 0 91250

result:

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

Test #56:

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

input:

ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...

output:



22317 19352 36850 75552

result:

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

Test #57:

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

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

input:

ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba
aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab
abbbbaabaa

output:



1 7 43 99

result:

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