QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#89570#5256. InsertionsdaydreamAC ✓290ms193136kbC++146.5kb2023-03-20 16:31:132023-03-20 16:31:17

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-20 16:31:17]
  • 评测
  • 测评结果:AC
  • 用时:290ms
  • 内存:193136kb
  • [2023-03-20 16:31:13]
  • 提交

answer

#include<bits/stdc++.h>
#define db double
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define LL long long
#define ldb long double
#define pdd pair<db,db>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pii pair<int,int>
#define pip pair<int,pii>
#define ppi pair<pii,int>
#define ppp pair<pii,pii>
#define pss pair<pair<char,char>,pair<char,char>>
#define fr first
#define sc second
#define mp make_pair
#define id(x,y) ((x-1)*m+y)
using namespace std;
const int mxn=4e5+10,mxm=5010,N=1e6,infi=1e9,mod=998244353,inv2=(mod+1)/2,inv3=(mod+1)/3;
const int v1=37,v2=53,M1=323323323,M2=998244353;
const int dx[]={0,1,0,-1},
	dy[]={1,0,-1,0};
const db PI=acos(-1),eps=1e-10;
const LL infl=1e18;
int DB_cmp(db x,db y) {if(fabs(x-y)<eps) return 0; if(x<y) return -1; return 1;}
inline void chkmax(LL &x,const LL y) {if(y>x) x=y;}
inline void chkmax(int &x,const int y) {if(y>x) x=y;}
inline void chkmin(LL &x,const LL y) {if(y<x) x=y;}
inline void chkmin(int &x,const int y) {if(y<x) x=y;}
inline void upd(int &x,const int y) {if((x+=y)>=mod) x-=mod;}
inline int Add(const int x,const int y) {if(x+y>=mod) return x+y-mod; return x+y;}
inline LL my_gcd(LL a,LL b) {if(!a||!b) return a|b; for(LL c=a%b;c;a=b,b=c,c=a%b); return b;}
inline int _pow(int k,int i)
{
	int t=1;
	for(;i;i>>=1,k=1ll*k*k%mod)
		if(i&1)
			t=1ll*t*k%mod;
	return t;
}
inline int _pow(int k,int i,int M)
{
	int t=1;
	for(;i;i>>=1,k=1ll*k*k%M)
		if(i&1)
			t=1ll*t*k%M;
	return t;
}
struct SAM
{
	int tim,siz[mxn],son[mxn],dep[mxn],top[mxn],dfn[mxn];
	int tp,nw,ps[mxn],ln[mxn],fa[mxn],trs[mxn][27];
	int f[mxn];
	int t,h[mxn];
	struct Tre
	{
		int to,nxt;
	}e[mxn];
	void add(int u,int v) {e[++t]=(Tre){v,h[u]};h[u]=t;}
	int build(int u,int c,int i)
	{
		int v,x=++tp;ps[i]=x;ln[x]=ln[u]+1;
		for(;u&&!trs[u][c];trs[u][c]=x,u=fa[u]);
		if(!u) fa[x]=1;
		else if(ln[v=trs[u][c]]==ln[u]+1) fa[x]=v;
		else
		{
			fa[++tp]=fa[v];ln[tp]=ln[u]+1;fa[x]=fa[v]=tp;
			for(int i=0;i<27;++i) trs[tp][i]=trs[v][i];
			for(;u&&trs[u][c]==v;trs[u][c]=tp,u=fa[u]);
		}
		return x;
	}
	void dfs1(int u)
	{
		int v;siz[u]=1;
		for(int i=h[u];i;i=e[i].nxt)
		{
			dep[v=e[i].to]=dep[u]+1;
			dfs1(v);siz[u]+=siz[v];
			if(siz[v]>siz[son[u]]) son[u]=v;
		}
	}
	void dfs2(int u,int Top)
	{
		top[u]=Top;dfn[u]=++tim;
		if(son[u]) dfs2(son[u],Top);
		int v;
		for(int i=h[u];i;i=e[i].nxt)
			if((v=e[i].to)!=son[u])
				dfs2(v,v);
	}
	void build(char *s,int L)
	{
		tp=nw=1;
		for(int i=L;i;--i) nw=build(nw,s[i]-'a',i);
		for(int i=2;i<=tp;++i) add(fa[i],i);
		assert(tp<=mxn);
		dfs1(1);dfs2(1,1);
	}
	int lcm(int x,int y)
	{
		int u=ps[x],v=ps[y];
		for(;top[u]!=top[v];u=fa[top[u]])
			if(dep[top[u]]<=dep[top[v]])
				swap(u,v);
		if(dep[u]<dep[v]) return ln[u];
		return ln[v];
	}
	void upd(int x) {f[ps[x]]++;}
	void work(int u=1)
	{
		int v;
		for(int i=h[u];i;i=e[i].nxt)
			f[v=e[i].to]+=f[u],
			work(v);
	}
	int qry(int x) {return f[ps[x]];}
}S1,S2,S3;
int n,L1,L2,L3,ans1,ans2,ans3,ans4,cnt[mxn],res[mxn];
char s[mxn],t[mxn],p[mxn],S[mxn];
map<pii,int> ex;
vector<pii> Q[mxn];
vector<int> ins[mxn],del[mxn];
struct BIT
{
	int n,tr[mxn];
	void upd(int i,int v) {for(;i<=n;i+=(i&-i)) tr[i]+=v;}
	void upd(int l,int r,int v) {upd(l,v); upd(r+1,-v);}
	int qry(int i) {int res=0; for(;i;i-=(i&-i)) res+=tr[i]; return res;}
}T;
LL rd()
{
	static LL sl,fh,ch;
	sl=0;fh=1;ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') fh=-1; ch=getchar();}
	while('0'<=ch&&ch<='9') sl=sl*10+ch-'0',ch=getchar();
	return sl*fh;
}
int main()
{
//	freopen("data.in","r",stdin);
//	for(int TT=rd();TT;--TT)
	{
		scanf("%s%s%s",s+1,t+1,p+1);
		L1=strlen(s+1);L2=strlen(t+1);L3=strlen(p+1);
		n=0;
		for(int i=1;i<=L1;++i) S[++n]=s[i];
		S[++n]='z'+1;
		for(int i=1;i<=L3;++i) S[++n]=p[i];
		S1.build(S,n);
		n=0;
		for(int i=1;i<=L3;++i) S[++n]=p[i];
		S[++n]='z'+1;
		for(int i=1;i<=L1;++i) S[++n]=s[i];
		reverse(S+1,S+n+1);
		S2.build(S,n);
		int x,y;
		
		ex.clear();
		x=y=0;
		for(int c,i=1;i<L3;++i)
		{
			c=p[i]-'a'+1;
			x=(1ll*x*v1+c)%M1;
			y=(1ll*y*v2+c)%M2;
			ex[mp(x,y)]=i+1;
		}
		x=y=0;
		for(int c,i=L2,vx=1,vy=1;i;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
		{
			c=t[i]-'a'+1;
			x=(1ll*vx*c+x)%M1;
			y=(1ll*vy*c+y)%M2;
			if(ex.count(mp(x,y))) S1.upd(ex[mp(x,y)]+L1+1);
		}
		
		ex.clear();
		x=y=0;
		for(int c,i=L3,vx=1,vy=1;i>1;--i,vx=1ll*v1*vx%M1,vy=1ll*v2*vy%M2)
		{
			c=p[i]-'a'+1;
			x=(1ll*vx*c+x)%M1;
			y=(1ll*vy*c+y)%M2;
			ex[mp(x,y)]=i-1;
		}
		x=y=0;
		for(int c,i=1;i<=L2;++i)
		{
			c=t[i]-'a'+1;
			x=(1ll*x*v1+c)%M1;
			y=(1ll*y*v2+c)%M2;
			if(ex.count(mp(x,y))) S2.upd(n-ex[mp(x,y)]+1);
		}
		S1.work();S2.work();
		for(int i=1;i<=L1;++i) cnt[i]=cnt[i-1]+(S1.lcm(i,L1+2)==L3);
//		for(int i=1;i<=L1;++i) printf("%d ",S1.lcm(i,L1+2)==L3);puts("");
		for(int i=0;i<=L1;++i)
		{
			res[i]+=cnt[L1]-cnt[i];
			if(i-L3+1>=0) res[i]+=cnt[i-L3+1];
			res[i]+=S1.qry(i+1)+S2.qry(n-i-L3);
		}
		if(L3<=L2)
		{
			n=0;
			for(int i=1;i<=L2;++i) S[++n]=t[i];
			S[++n]='z'+1;
			for(int i=1;i<=L3;++i) S[++n]=p[i];
			S3.build(S,n);
			int num=0;
			for(int i=1;i<=L2;++i) num+=(S3.lcm(i,L2+2)==L3);
			for(int i=0;i<=L1;++i) res[i]+=num;
		}
		else if(L3>=L2+2)
		{
			T.n=S2.tp;
			x=y=0;int vx=1,vy=1;
			for(int c,i=1;i<=L2;++i)
			{
				c=t[i]-'a'+1;
				x=(1ll*x*v1+c)%M1;
				y=(1ll*y*v2+c)%M2;
				vx=1ll*vx*v1%M1;vy=1ll*vy*v2%M2;
			}
			pii ht=mp(x,y);vx=M1-vx;vy=M2-vy;
			x=y=0;
			for(int c,i=1;i<=L2;++i)
			{
				c=p[i]-'a'+1;
				x=(1ll*x*v1+c)%M1;
				y=(1ll*y*v2+c)%M2;
			}
			for(int c,i=L2+1;i<L3;++i)
			{
				c=p[i]-'a'+1;
				x=(1ll*x*v1+c)%M1;
				y=(1ll*y*v2+c)%M2;
				c=p[i-L2]-'a'+1;
				x=(1ll*vx*c+x)%M1;
				y=(1ll*vy*c+y)%M2;
				if(mp(x,y)==ht)
				{
					int u,v;
					u=S1.ps[i+1+L1+1];
					v=S2.ps[n-(i-L2)+1];
					ins[S1.dfn[u]].pb(v);
					del[S1.dfn[u]+S1.siz[u]].pb(v);
				}
			}
			for(int i=1;i<L1;++i) Q[S1.dfn[S1.ps[i+1]]].pb({i,S2.ps[n-i-L3]});
			for(int i=1;i<=S1.tp;++i)
			{
				for(auto u:ins[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,1);
				for(auto u:del[i]) T.upd(S2.dfn[u],S2.dfn[u]+S2.siz[u]-1,-1);
				for(auto x:Q[i]) res[x.fr]+=T.qry(S2.dfn[x.sc]);
			}
		}
		ans1=-1;
		for(int i=0;i<=L1;++i)
		{
			if(res[i]>ans1) ans1=res[i],ans2=1,ans3=ans4=i;
			else if(res[i]==ans1) ans2++,ans4=i;
		}
		printf("%d %d %d %d\n",ans1,ans2,ans3,ans4);
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 34268kb

input:

rrddrrrdd
ddrrd
rrddrr

output:

2 2 6 7

result:

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

Test #2:

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

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

input:

wgwwggggw
g
gggg

output:

2 5 4 8

result:

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

Test #4:

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

input:

q
uuquu
u

output:

4 2 0 1

result:

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

Test #5:

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

input:

gpgggpppg
pg
gpgg

output:

2 1 4 4

result:

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

Test #6:

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

input:

p
xpxp
p

output:

3 2 0 1

result:

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

Test #7:

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

input:

aacaacacaa
ca
caca

output:

2 5 2 9

result:

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

Test #8:

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

input:

k
kekekkekk
k

output:

7 2 0 1

result:

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

Test #9:

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

input:

ghhhhg
g
ghhg

output:

2 1 3 3

result:

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

Test #10:

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

input:

b
xbb
b

output:

3 2 0 1

result:

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

Test #11:

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

input:

nddnnndndn
dnd
ndndn

output:

3 1 5 5

result:

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

Test #12:

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

input:

imiimmmm
miimi
i

output:

6 9 0 8

result:

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

Test #13:

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

input:

gzzzzzzzzz
zgzzzg
gzgggzzz

output:

0 11 0 10

result:

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

Test #14:

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

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

input:

jmmmmjmmj
jmjjjmjm
mjmmmmjj

output:

0 10 0 9

result:

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

Test #16:

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

input:

f
ffffwff
wffw

output:

0 2 0 1

result:

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

Test #17:

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

input:

plpll
llplll
pppppppl

output:

0 6 0 5

result:

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

Test #18:

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

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

input:

okkkkkok
okokkkoo
kookooko

output:

0 9 0 8

result:

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

Test #20:

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

input:

ccc
cpppp
cc

output:

3 1 3 3

result:

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

Test #21:

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

input:

yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...

output:

631 1000 0 999

result:

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

Test #22:

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

input:

annnnnnnnnnnnnnnnnnnnannnnnannannnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnannnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnaannnnnnannnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnnnnnnnannannnnnnnnannnnnnnannannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnan...

output:

0 1000 0 999

result:

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

Test #23:

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

input:

atatatataaaaaattattaaataataaaatttattattaaaataaattaaatattaaaataaaattatataatttaatattttattaatatattattatttaaattttaaaaattaaattttttaatttaattatttaaaataatttttattaaatttatttatattataaatttattataaatatttatatattttttatattatattatttaatttttttaaaatttaattttatttattttattatatataatttaaaataatttttttaaaaatattattttatttaaaatatat...

output:

0 1000 0 999

result:

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

Test #24:

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

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 413 587 999

result:

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

Test #25:

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

input:

rlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrlrl...

output:

315 2 1 998

result:

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

Test #26:

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

input:

huhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuuuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhuhu...

output:

260 1 113 113

result:

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

Test #27:

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

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

748 907 0 906

result:

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

Test #28:

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

input:

kkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkpkppkkkkkkpkkkkkkkkkkkkkkkpkkkkkkkkkkkppkkpkkkkkkkkkkkpkkpkpkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkpkkkkkpkkkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkkpkpkkkkkkkpkkkkkkkkkkkkkkkkkkkkkpkkkkkkkkkkkkkkpkkkkkkpkkkkkkkkkkkkkkkkkkkpkkkpkkkkkpkkkkkkkpkpk...

output:

0 907 0 906

result:

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

Test #29:

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

input:

illillliiiiiilliiilliiilliliilililiililiiililililliliililiillilliliiiiiliiillllllllilliiilililiililililliiiliiililiillillliliiiliiliiliililllliiliiililiilllilllllliiliiiillilillllllillllililililliiiiliilliililllllilliliiiiilililiiiillliiillliililllilliiiiiilliilllllllliillllliiiiiiilliiliilllliiliil...

output:

0 907 0 906

result:

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

Test #30:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

1 702 0 701

result:

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

Test #31:

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

input:

mymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymymy...

output:

374 454 0 906

result:

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

Test #32:

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

input:

kckckckckckckckckckckckckckckckckckckckckckckckccckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckckc...

output:

291 370 50 788

result:

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

Test #33:

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

input:

iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...

output:

937 966 0 965

result:

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

Test #34:

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

input:

apaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaapapaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaapaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaapaaaapapappaaaaaaaapaaappaaaapaapapaaaaaaapaaaappaaapaaaaaaaaaaaaaaaaaaaaaaaaaaaaaapaaaaaapaaaaaaaapaaaapppaapaaaaaaaaaaaapppaapaaaaaaaaaaaaaaaaaaaaaaapaaaaaaaaaaaaaaaaaaaaaaaa...

output:

35 64 600 663

result:

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

Test #35:

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

input:

msmmssmmsmmmsmssmmmmmsmmmsmssssssssmmmmssmmsmmsmmmsmssmmmmsssmmsmmmssmssmsmmmsmssmsmmmsmmmsmssmsssmmssssmmmssmmssssmsmsmsmmmsmsmmsmsmssssssssmmmmmmsmmmsssmmmssssssssssmmmmssmsmsmmsmssssssssmmsmmsssmssmmmssssmsssmssmssmsmsmsmsmmsmmssmmsmmsmsmmssmmssmsmssmsssmsmsmsmmmmsmssmmmmsmmssmmmssssmsssssmmssmmm...

output:

0 966 0 965

result:

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

Test #36:

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

input:

nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...

output:

1 768 0 767

result:

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

Test #37:

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

input:

jrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjrjr...

output:

468 483 0 964

result:

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

Test #38:

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

input:

dkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkkkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdkdk...

output:

429 443 80 964

result:

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

Test #39:

score: 0
Accepted
time: 133ms
memory: 113000kb

input:

tttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttttt...

output:

44459 99774 0 99773

result:

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

Test #40:

score: 0
Accepted
time: 187ms
memory: 142276kb

input:

annnannnnnnnnnnnnnnnnnnnannnnnnnnnnannnnnnnnnnnnnnannananannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnnnnnnnnnnnnannnnannnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnnnnnnnnnnannnnnnnnnnnnnnnnnnnnannnnnnnaannnnnnnnnnnnnnnnnnnnnannannnnnnnnnnnnannnannnnnnnnannnnnnnnnnnnnnnnnnnnnannnannnaannan...

output:

0 99774 0 99773

result:

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

Test #41:

score: 0
Accepted
time: 273ms
memory: 161196kb

input:

eyyeeeyyeyyeyeyyeyeeyyyyeeeeeyyyyeeeeyyyyyyyyyyyeeeeeeeeyeyyyeyyeeyyyeeyeeeeyeeyeeeeeeyyyeeyeeyeeeyyeyeyyeyyeyeyyyeyyeeeeeyeyyyyyeyyeyeyeeyyyyyeeyeyeeeyeeeyyyeeyeeyyyeeyyyeeyeyyeeeeyeyeeeyyeeyyeyeyyeeyyeyyyyeeeyyyeyyyeyyeeyeeeeeeyyyeyeyeyeeeeeyeyeyeyyeyeyyyyyyeyeeyeyyyeeeyeeyyeeyyyeyeyeyeyyyyyyeeeey...

output:

0 99774 0 99773

result:

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

Test #42:

score: 0
Accepted
time: 140ms
memory: 115716kb

input:

ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

1 61041 38733 99773

result:

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

Test #43:

score: 0
Accepted
time: 135ms
memory: 127072kb

input:

zqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzqzq...

output:

22229 2 1 99772

result:

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

Test #44:

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

input:

babababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...

output:

22229 2 1 99772

result:

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

Test #45:

score: 0
Accepted
time: 151ms
memory: 103920kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

85548 90750 0 90749

result:

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

Test #46:

score: 0
Accepted
time: 236ms
memory: 132424kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbobbobbbbbobbbobbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbobbbbbbbbbbbobbbbbbbboobbobbbbbbbbbbobbbbbbbbbbbbbbbobbbbobbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbobbbbbbbbbbbbbobbbbbbbbbbbbbbbbboobbbbbobbbbbbbbbbbbbbbbbobbbbbbbbbbbbbbbbbbbbbbbbobbbobobbobbbbbbbbbbbbbbbbbbobbbbbbbobbbbbb...

output:

0 90750 0 90749

result:

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

Test #47:

score: 0
Accepted
time: 289ms
memory: 152160kb

input:

llrlrrlrlrrllrrrrrlrlrlllllrrrrllrllrrllllrrlrlrllllllrrrlrllllllrrrlrrrrlrlrllrrrrrrrrlrlrrrlrrlrlllllrllrllrlrlllrrrrllllllllllrrrllrrlllrlrllrrrlllrrllrrrlllrlrlrlrlrlrllrlrrrrrrlrlrrllrrrrrrllrllrrlrlrlllrrrlrrrlrrrrrrrrrlrlllrlrlrlrlrllllrlrrrrrlllrlllrlrrlrrrlrlrllrrrrlllllllrllrlrlllllrrrrrrr...

output:

0 90750 0 90749

result:

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

Test #48:

score: 0
Accepted
time: 159ms
memory: 115908kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

1 71220 19530 90749

result:

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

Test #49:

score: 0
Accepted
time: 161ms
memory: 119152kb

input:

qoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqoqo...

output:

42774 45375 0 90748

result:

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

Test #50:

score: 0
Accepted
time: 135ms
memory: 119812kb

input:

xtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxtxt...

output:

40492 43093 2508 88692

result:

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

Test #51:

score: 0
Accepted
time: 153ms
memory: 124896kb

input:

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

97181 91251 0 91250

result:

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

Test #52:

score: 0
Accepted
time: 225ms
memory: 149892kb

input:

vvvvvvvvvvvvvvvvvvmmvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvmvvvvvvvmvvvvvvmvvmvmvmvmvvvvvvvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvvvvvmvvvvvvvvvvvvvvvvvmvmvvvvvvvvvvmmvvvvvvvvvvvvvvvmvvmvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv...

output:

6028 98 22809 22906

result:

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

Test #53:

score: 0
Accepted
time: 290ms
memory: 193136kb

input:

qxqxqxxxxqxqxqqxqqqxqxxxqxqqxxxxqqqqqxxqqxqqqxxxqxxqqxxqxqqxxxxqxxqxqqqxxqqxxqqxqxxxxxxqxqqqqqxxqxqqxxqxqqxxxxxxqxqxqxqqqqqqxxqqqxqqqqqqxqxxqqqxxxqxxqxqqqxxxxqxxxxqqqxxxxqqxqxqqxxqqqqqxqxxqxxxxqxxxxxqqqxxqqqqxqxqqqxqxxxxxqxxqxqqxqxqxxqqqxqqqqxxxxxqxxqxxqqxqxqxqqqqxqxqxqxxxxqxxqqxqqxqqxxxxxqqxxqxqqqq...

output:

0 91251 0 91250

result:

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

Test #54:

score: 0
Accepted
time: 145ms
memory: 148976kb

input:

wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww...

output:

1 4772 86479 91250

result:

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

Test #55:

score: 0
Accepted
time: 160ms
memory: 162472kb

input:

lglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglglg...

output:

48590 45626 0 91250

result:

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

Test #56:

score: 0
Accepted
time: 170ms
memory: 154124kb

input:

ibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibibib...

output:

22317 19352 36850 75552

result:

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

Test #57:

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

input:

abbababa
babbba
bbab

output:

2 6 1 7

result:

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

Test #58:

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

input:

ababbabaabbabbbabbaabababaaababaabaaababbbbabababbbbaaabbbabbbbaaabbbbbbbbaabaabaabbaaababbbbbabbbba
aabaaababaabaabababbbaaabbbbbbaabaabaaabbaaabababbaabbaabbab
abbbbaabaa

output:

1 7 43 99

result:

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