QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#67422#5014. 复读程度Y_B_X61 655ms106120kbC++149.7kb2022-12-10 14:05:342022-12-10 14:05:37

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-10 14:05:37]
  • 评测
  • 测评结果:61
  • 用时:655ms
  • 内存:106120kb
  • [2022-12-10 14:05:34]
  • 提交

answer

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int N=1e5+10;
int n,m;
char ch;
template<typename T>
inline void read(T &x){
	x=0;ch=getchar();while(ch<33)ch=getchar();
	while(ch>47)x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
void write(ull x){if(x>9)write(x/10);putchar(48|x%10);}
char s[N];
int id1[N<<1],id2[N<<1],tmp_id[N<<1],tmp_v[N<<1];
ull a[N],b[N];
inline void sort(int n,int *id,int V,int *v,bool b=0){
	static int cnt[N],i;
	memset(cnt,0,(V+1)<<2);
	for(i=1;i<=n;++i)++cnt[v[i]];
	if(b){for(i=V-1;~i;--i)cnt[i]+=cnt[i+1];}
	else {for(i=1;i<=V;++i)cnt[i]+=cnt[i-1];}
	for(i=1;i<=n;++i)id[cnt[v[i]]--]=i;
}
int rpos1[N],lpos2[N];
int ff1[N<<1][17],ff2[N<<1][17];
int mxlen1[N<<1],link1[N<<1];
int trans1[N<<1][26];
int h1[N<<1],to1[N<<1],nextn1[N<<1],edg1;
int mxlen2[N<<1],link2[N<<1];
int trans2[N<<1][26];
int h2[N<<1],to2[N<<1],nextn2[N<<1],edg2;
int tot1=1,tot2=1,last,tmp,x,y,xx,tt;
int posl1[N<<1],posr1[N<<1];
int posl2[N<<1],posr2[N<<1];
int occ1[N<<1],occ2[N<<1];
int dfn1[N<<1],dfnr1[N<<1],rev1[N<<1];
int dfn2[N<<1],dfnr2[N<<1],rev2[N<<1];
ull vl[N<<1],vr[N<<1];
inline void add1(int x,int y){
	to1[++edg1]=y,nextn1[edg1]=h1[x],h1[x]=edg1;
}
inline void add2(int x,int y){
	to2[++edg2]=y,nextn2[edg2]=h2[x],h2[x]=edg2;
}
void extend1(char a){
	y=last,tmp=++tot1;
	mxlen1[tmp]=mxlen1[y]+1; 
	for(;!trans1[y][a]&&y;y=link1[y])trans1[y][a]=tmp;
	if(!y)link1[tmp]=1;
	else {
		x=trans1[y][a];
		if(mxlen1[x]==mxlen1[y]+1)link1[tmp]=x;
		else {
			xx=++tot1;mxlen1[xx]=mxlen1[y]+1;
			memcpy(trans1[xx],trans1[x],104);
			link1[xx]=link1[x];posr1[xx]=posr1[x];
			for(;trans1[y][a]==x;y=link1[y])trans1[y][a]=xx;
			link1[x]=link1[tmp]=xx;
		}
	}
	last=tmp;
}
void extend2(char a){
	y=last,tmp=++tot2;
	mxlen2[tmp]=mxlen2[y]+1; 
	for(;!trans2[y][a]&&y;y=link2[y])trans2[y][a]=tmp;
	if(!y)link2[tmp]=1;
	else {
		x=trans2[y][a];
		if(mxlen2[x]==mxlen2[y]+1)link2[tmp]=x;
		else {
			xx=++tot2;mxlen2[xx]=mxlen2[y]+1;
			memcpy(trans2[xx],trans2[x],104);
			link2[xx]=link2[x];posl2[xx]=posl2[x];
			for(;trans2[y][a]==x;y=link2[y])trans2[y][a]=xx;
			link2[x]=link2[tmp]=xx;
		}
	}
	last=tmp;
}
void dfs1(int x){
	int i,y;rev1[dfn1[x]=++tt]=x;ff1[x][0]=link1[x];
	for(i=1;i!=17;++i)ff1[x][i]=ff1[ff1[x][i-1]][i-1];
	for(i=h1[x];y=to1[i];i=nextn1[i]){
		dfs1(y),vr[x]+=vr[y],occ1[x]+=occ1[y];
	}
	dfnr1[x]=tt;
}
void build1(){
	int i;last=1;
	for(i=1;i<=n;++i){
		extend1(s[i]),posr1[tmp]=i;
		vr[tmp]=b[i];rpos1[i]=tmp,occ1[tmp]=1;
	}
	for(i=2;i<=tot1;++i)posl1[i]=posr1[i]-mxlen1[i]+1;
	for(i=2;i<=tot1;++i)add1(link1[i],i);
	dfs1(1);
}
void dfs2(int x){
	int i,y;rev2[dfn2[x]=++tt]=x;ff2[x][0]=link2[x];
	for(i=1;i!=17;++i)ff2[x][i]=ff2[ff2[x][i-1]][i-1];
	for(i=h2[x];y=to2[i];i=nextn2[i]){
		dfs2(y),vl[x]+=vl[y],occ2[x]+=occ2[y]; 
		if(posl2[y]<posl2[x])posl2[x]=posl2[y];
	}
	dfnr2[x]=tt;
}
void build2(){
	int i;last=1;tt=0;
	for(i=n;i;--i){
		extend2(s[i]),posl2[tmp]=i;
		vl[tmp]=a[i];lpos2[i]=tmp,occ2[tmp]=1;
	}
	for(i=2;i<=tot2;++i)add2(link2[i],i);
	dfs2(1); 
	for(i=2;i<=tot2;++i)posr2[i]=posl2[i]+mxlen2[i]-1;
}
inline int get1(int l,int r){
	static int x,i;
	x=rpos1[r];l=r-l+1;
	for(i=16;~i;--i)if(mxlen1[ff1[x][i]]>=l)x=ff1[x][i];
	return x; 
}
inline int get2(int l,int r){
	static int x,i;
	x=lpos2[l];r=r-l+1;
	for(i=16;~i;--i)if(mxlen2[ff2[x][i]]>=r)x=ff2[x][i]; 
	return x;
}
int cn=1;
int ext1[N<<1],ext2[N<<1];
int sn1[N<<1],sn2[N<<1];
int p1[N<<1],p2[N<<1];
int *rp1[N<<1],rp1_[N<<1],*_rp1=rp1_;
int *rp2[N<<1],rp2_[N<<1],*_rp2=rp2_;
void build(){
	int i,j,k,l1,r2;
	sort(tot1,tmp_id,n,posr1,1);
	for(i=1;i<=tot1;++i)tmp_v[i]=posl1[tmp_id[i]];
	sort(tot1,id1,n,tmp_v);
	for(i=1;i<=tot1;++i)id1[i]=tmp_id[id1[i]];
	
	sort(tot2,tmp_id,n,posr2,1);
	for(i=1;i<=tot2;++i)tmp_v[i]=posl2[tmp_id[i]];
	sort(tot2,id2,n,tmp_v);
	for(i=1;i<=tot2;++i)id2[i]=tmp_id[id2[i]];
	k=2;
	for(i=2;i<=tot1;i=j){
		j=i;l1=posl1[id1[i]];
		while(posl2[id2[k]]<l1&&k<=tot2)++k;
		while(posl1[id1[j]]==l1){
			ext1[id1[j]]=cn;
			p1[id1[j]]=sn1[cn]++;
			if(posr1[id1[j]]==posr2[id2[k]])++cn,++k;
			++j;
		}
	}
	--cn;
	memcpy(tmp_id+1,id1+1,tot1<<2);
	for(i=1;i<=tot1;++i)tmp_v[i]=posr1[id1[i]];
	sort(tot1,id1,n,tmp_v);
	for(i=1;i<=tot1;++i)id1[i]=tmp_id[id1[i]];

	memcpy(tmp_id+1,id2+1,tot2<<2);
	for(i=1;i<=tot2;++i)tmp_v[i]=posr2[id2[i]];
	sort(tot2,id2,n,tmp_v);
	for(i=1;i<=tot2;++i)id2[i]=tmp_id[id2[i]];
	k=2;
	for(i=2;i<=tot2;i=j){
		j=i;r2=posr2[id2[i]];
		while(posr1[id1[k]]<r2&&k<=tot1)++k;
		while(posr2[id2[j]]==r2){
			ext2[id2[j]]=ext1[id1[k]];
			p2[id2[j]]=sn2[ext1[id1[k]]]++;
			if(posl1[id1[k]]==posl2[id2[j]])++k;
			++j;
		}
	}
	for(i=1;i<=cn;++i)rp1[i]=_rp1,_rp1+=sn1[i];
	for(i=1;i<=cn;++i)rp2[i]=_rp2,_rp2+=sn2[i];
	for(i=2;i<=tot1;++i)p1[i]=sn1[ext1[i]]-p1[i]-1;
	for(i=2;i<=tot2;++i)p2[i]=sn2[ext2[i]]-p2[i]-1;
	for(i=2;i<=tot1;++i)x=id1[i],rp1[ext1[x]][p1[x]]=x;
	for(i=2;i<=tot2;++i)x=id2[i],rp2[ext2[x]][p2[x]]=x;
}
ull ans[N];
ull s_[N<<1],ss_[N<<1],*_s=s_,*_ss=ss_;
int id_[N<<1],bl_[N<<1],*_id=id_,*_bl=bl_; 
struct Block{
	ull *s,*ss;int *id,*bl;int n,nn,il;
	inline void init(int n_){
		n=n_;s=_s,ss=_ss,id=_id,bl=_bl;
		_s+=n,_ss+=n,_id+=n,_bl+=n;
		nn=sqrt(n);int i;
		for(i=0,n_=0;i<n;i+=nn,++n_)id[i]=n_,bl[i]=i;
		for(i=1;i<n;++i)id[i]||(id[i]=id[i-1],bl[i]=bl[i-1]);
	}
	inline void upd(int i,ull v){
		il=bl[i];for(;i>=il;--i)s[i]+=v;
		if(~i)for(i=id[i];~i;--i)ss[i]+=v;
	}
	inline ull inq(int i){return s[i]+ss[id[i]];}
}B[N<<1];
ull res;
struct Step2{
	int id[N<<1],m,nn;
	struct inq{
		int x,y,i,idx;bool o;inq()=default;
		inq(int _x,int _y,int _i,bool _o):
			x(_x),y(_y),i(_i),o(_o){}
		inline bool operator <(const inq &a)const {
			return idx!=a.idx?idx<a.idx:idx&1?y<a.y:y>a.y;
		}
	}q[N<<2];
	inline void add(int x,int y,int i){
		q[++m]=inq(dfnr1[x],dfnr2[y],i,1);
		q[++m]=inq(dfn1[x],dfnr2[y],i,0);
		q[++m]=inq(dfnr1[x],dfn2[y],i,0);
		q[++m]=inq(dfn1[x],dfn2[y],i,1); 
	}
	int X,Y,x,y;
	struct Edge{
		int h[N<<1],l[N<<2],r[N<<2],nextn[N<<2],edg;
		ull dt[N<<2];
		inline void add(int x,int _l,int _r){
			++edg;l[edg]=_l,r[edg]=_r;
			nextn[edg]=h[x],h[x]=edg;
		}
		inline void inq(bool b){
			++edg;
			b?res+=dt[edg]:res-=dt[edg];
		}
	}Ex,Ey;
	#define ForE(E) for(j=E.h[i];j;j=E.nextn[j])
	void solve(){
		if(!m)return;
		int i,j,l,r;
		nn=tot1/sqrt(m);nn||(nn=1);
		for(i=tot1;i;--i)id[i]=(i-1)/nn+1;
		for(i=1;i<=m;++i)q[i].idx=id[q[i].x];
		sort(q+1,q+m+1);
		X=1,Y=1;
		for(i=1;i<=m;++i){
			x=q[i].x,y=q[i].y;
			if(Y<y)Ex.add(X,Y,y),Y=y;
			if(y<Y)Ex.add(X,y,Y),Y=y;
			if(X<x)Ey.add(Y,X,x),X=x;
			if(x<X)Ey.add(Y,x,X),X=x;
		}
		for(i=1;i<=cn;++i)B[i].init(sn2[i]);
		ull v;
		for(i=2;i<=tot1;++i){
			x=rev1[i];
			B[ext1[x]].upd(mxlen1[x]-mxlen1[link1[x]]-1,vr[x]*occ1[x]);
			ForE(Ex){
				l=Ex.l[j];v=0;
				for(r=Ex.r[j];r>l;--r){
					y=rev2[r];
					v+=B[ext2[y]].inq(p2[y])*vl[y];
				}
				Ex.dt[j]=v;
			}
		}
		memset(s_,0,tot2<<3);
		memset(ss_,0,tot2<<3);
		memset(id_,0,tot2<<3);
		_s=s_,_ss=ss_,_id=id_,_bl=bl_; 
		for(i=1;i<=cn;++i)B[i].init(sn1[i]);
		for(i=2;i<=tot2;++i){
			y=rev2[i];
			B[ext2[y]].upd(mxlen2[y]-mxlen2[link2[y]]-1,vl[y]*occ2[y]);
			ForE(Ey){
				l=Ey.l[j];v=0;
				for(r=Ey.r[j];r>l;--r){
					x=rev1[r];
					v+=B[ext1[x]].inq(p1[x])*vr[x];
				}
				Ey.dt[j]=v;
			}
		}
		X=1,Y=1;
		Ex.edg=Ey.edg=0;
		for(i=1;i<=m;++i){
			x=q[i].x,y=q[i].y;
			if(Y<y)Ex.inq(1),Y=y;
			if(y<Y)Ex.inq(0),Y=y;
			if(X<x)Ey.inq(1),X=x;
			if(x<X)Ey.inq(0),X=x;
			ans[q[i].i]+=q[i].o?res:-res;
		}
	} 
}Z;
struct Step1{
	struct bit{
		ull t[N<<1],res;int n;
		inline void clr(){memset(t+1,0,n<<3);}
		inline void clr(int i){for(;i<=n;i+=i&(-i))t[i]=0;}
		inline void upd(int i,ull v){for(;i<=n;i+=i&(-i))t[i]+=v;}
		inline ull inq(int i){for(res=0;i;i-=i&(-i))res+=t[i];return res;}
	}T;
	struct inq{
		int ext,r,vl,vr,i;ull mul;inq()=default;
		inq(int _ext,int _r,int _vl,int _vr,ull _mul,int _i):
			ext(_ext),r(_r),vl(_vl),vr(_vr),mul(_mul),i(_i){}
		inline bool operator <(const inq &a)const {
			return ext!=a.ext?ext<a.ext:r<a.r;
		}
	}q1[N],q2[N];
	int qtot1,qtot2,x,y;
	inline void add1(int x,int _r,int y,ull mul,int i){
		q1[++qtot1]=inq(ext1[x],_r,dfn2[y],dfnr2[y],mul,i);
	}
	inline void add2(int y,int _r,int x,ull mul,int i){
		q2[++qtot2]=inq(ext2[y],_r,dfn1[x],dfnr1[x],mul,i);
	}
	void solve1(inq *q){
		T.n=tot2;
		sort(q+1,q+qtot1+1);
		int i,j=0,l,extp=-1;
		for(i=1;i<=qtot1;++i){
			if(q[i].ext!=extp){
				for(l=0;l<j;++l)T.clr(dfn2[rp2[extp][l]]);
				extp=q[i].ext,j=0;
			}
			while(j<=q[i].r){
				x=rp2[extp][j++],T.upd(dfn2[x],vl[x]);
			}
			ans[q[i].i]+=(T.inq(q[i].vr)-T.inq(q[i].vl))*q[i].mul;
		}
	}
	void solve2(inq *q){
		T.clr();T.n=tot1;
		sort(q+1,q+qtot2+1);
		int i,j=0,l,extp=-1;
		for(i=1;i<=qtot2;++i){
			if(q[i].ext!=extp){
				for(l=0;l<j;++l)T.clr(dfn1[rp1[extp][l]]);
				extp=q[i].ext,j=0;
			}
			while(j<=q[i].r){
				x=rp1[extp][j++],T.upd(dfn1[x],vr[x]);
			}
			ans[q[i].i]+=(T.inq(q[i].vr)-T.inq(q[i].vl))*q[i].mul;
		}
	}
	void solve(){solve1(q1);solve2(q2);} 
}S;
int main(){
	int i,l1,r1,l2,r2,u,v;
	read(m),read(m);
	while(ch<33)ch=getchar();
	while(ch>96)s[++n]=ch-97,ch=getchar();
	for(i=1;i<=n;++i)read(a[i]);
	for(i=1;i<=n;++i)read(b[i]);
	build1();
	build2();
	build();
	for(i=1;i<=m;++i){
		read(l1),read(r1);y=get2(l1,r1);
		read(l2),read(r2);x=get1(l2,r2);
		u=posr1[x]-posl1[x]-r2+l2;
		v=posr2[y]-posl2[y]-r1+l1;
		if(ext1[x]==ext2[y]&&p2[y]<=u&&p1[x]<=v)ans[i]=vr[x]*vl[y]*occ1[x];
		if(h2[y])S.add1(x,u,y,vr[x]*occ1[x],i);
		if(h1[x])S.add2(y,v,x,vl[y]*occ2[y],i);
		if(h1[x]&&h2[y])Z.add(x,y,i);
	}
	S.solve();
	Z.solve();
	for(i=1;i<=m;++i)write(ans[i]),putchar('\n');
}

详细

Subtask #1:

score: 7
Accepted

Test #1:

score: 7
Accepted
time: 4ms
memory: 4048kb

input:

500 500
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

15720454042420499810
4058077030882532408
14651762045124606089
4030024243931986061
18033423360813892607
9470601111824364484
3883374861354698625
16650831689368240202
8339028189650687576
2683289915379600554
13133811958066776394
14181220923901262251
18173739360450512256
13142314545999179754
148925491596...

result:

ok 500 lines

Test #2:

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

input:

500 500
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszz...

output:

4843650749197240262
7777110205341291111
533576317536031175
16712994243500559204
9988085877723856684
9644193924482321332
3247342125341043527
18152622312040037224
13045121434804725850
10593529771756855740
13316626648976199221
6181092693273210423
9148547538129213975
9376364571107435561
2140403332478526...

result:

ok 500 lines

Test #3:

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

input:

500 500
aaaaabbaabbabbbaabaabbabbabbbaaabaaaabbbbbbaaabaabbbbbbaabbaaaaababbaaaaabbbbababbabaabbbbbbbbaaaaaaabaabbabbbbaabbaabaaabbbabbaabbbabaabaaaaababbaabbabbbabbababbbaabbabaaabbbbaaabbbabbabaabbabbaaabbaabbabbbbaaaaaababaaaabaababbaabbabbabbbabbaabbbaabbaaababaaabbababbbabaababaabbbbbabbababaab...

output:

841375054012212333
13406426787139944226
6541986259052503362
10583258635957015782
11582649090627508617
4747829250201069768
11571422754704651998
14603866222879735665
8438246043626601023
16155298152184479844
9052925087624568857
18388444310571976215
13304308468056840286
18125780089857220122
363421144082...

result:

ok 500 lines

Test #4:

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

input:

500 500
sulasusulasusulasulasulsulasusulasususulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasulasulsulasulasulsulasususulasulasulsulasulasulsulasulasulsulasusulasulasulsulasulasulsulasusulasusulasusulas...

output:

2320755102639148175
17108462705447992416
6030359132551843296
889683039894413148
10901851555398837076
1991544941914879425
9087724446342520941
5134546535199286414
12947484109492427089
5962550827492657739
4877066450610765849
6699323319072695780
11167645157062070624
13985172887966350800
8075429763917070...

result:

ok 500 lines

Test #5:

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

input:

500 500
bbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbfyfzxjdqlcaadccvsbbbbbbqouvtudkzorrxinacvncytgmtbbbbbbbbbbbbqouvtudkzorrx...

output:

18295637548117042088
6105463594888898313
15681140870484623884
17957090271580958329
11763132903578154240
17769627666201366836
16493946443969420940
12712093409624537595
2436698665645215125
8863273927617841787
5065586857868462806
8771649105206144878
6715985691821336097
8851433094837196039
7055234226266...

result:

ok 500 lines

Test #6:

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

input:

500 500
yyyayyayyyayyayyyayyayyyayyyayyyayyayyyyayyayyyayyyayyayyyayyyayyayyayyyyayyyayyyayyayyayyyayyayyayyyayyayyayyyayyyyyayyayyyyayyayyyayyayyyayyyayyyayyayyyayyayyyyayyyayyayyayyyayyayyyayyyyayyyyayyayyyayyayyayyyayyayyayyyyayyayyyayyayyayyyayyyyayyayyayyyayyayyayyyayyayyayyyyayyyayyyayyyyayyay...

output:

6159560444195180556
5294852391541430076
6195718271241091926
7959984071139675340
1598729415848168155
4879964117998052348
2279721248493220290
2026655128556749470
9803272548967597498
1028236064772678471
5410852487707111065
3600180224455323043
60239358603452318
2179897463397058094
16626503365867372202
3...

result:

ok 500 lines

Test #7:

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

input:

500 500
fffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffxfqifffnmogfffxfqifffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqifffffffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqifffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfffxfqiffffffffxfqifffnmogfff...

output:

6263422992304461664
10533199195660359295
11930245273187149005
380050211417129795
8399013088311259527
7005867409130681392
6872331929648615383
11661502418569897193
18027795221888639599
8932010711134684820
6331436398298306214
14599171184201697655
16632037523890780117
10373998601812781913
16089838760431...

result:

ok 500 lines

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #8:

score: 15
Accepted
time: 14ms
memory: 8896kb

input:

5000 5000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

12046186417900804485
3907200386448639860
16785470842023310270
13867397394972404837
17085398553187209926
11495532885795119226
12151570815045120790
4174337022608077877
6326694597133262496
5169007805286709535
14463367619086789683
627371028328452442
16378439470252322552
8286285259552634235
4646456254657...

result:

ok 5000 lines

Test #9:

score: 0
Accepted
time: 14ms
memory: 8468kb

input:

5000 5000
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzs...

output:

735272585091871492
2425556370857741242
8489901764977622765
9888756352722135114
3110111362923242403
9113727892967247055
13146817111311386931
5955980702194075793
11763307103994511020
11636340521260903139
13880517640770645879
18280247001976771986
9041182678245966519
902847942097731925
17037540142883387...

result:

ok 5000 lines

Test #10:

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

input:

5000 5000
bababbaabbbbbabbabaababbbaabababbbbaaabbaabbbbaaabaaaaabbababaababbbabbabbaaabbaaaaaababbababbbbbabbbbbaaabbabababaaababbababaabaaaaaabaaabbabaaaabaabaaaaaabbaaaaaaabbbbbabbabababbbabababaabaabbbbbabaabbbaaabbaaababbabaabaabbababaaaaaaabaaaabaabbbabbaaaababbabbaaabbbbabbabbaabbabbbbabaabbb...

output:

14997976760389310587
15623438489514479805
3150343034406864174
3816221098639928267
9378704101760633024
7513129444188437491
13447233088170491140
9761793475353455477
14533020333667464089
3755460369265761557
1017346093533703703
13617526768501762999
3768834851789866303
6158131626925412903
362975187944345...

result:

ok 5000 lines

Test #11:

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

input:

5000 5000
faffafimufxzbzetkfeqjfaffafxwgaqswmswhlkteloiarwwdafaffafimufxzbzetkfeqjfaffaffaffafimufxzbzetkfeqjfaffafxwgaqfaffafimufxzbzetkfeqjfaffafxwgaqswmswhlkteloiarwwdafaffafimufxzbzetkfeqjfaffaffaffafimufxzbzetkfeqjfaffafxwgaqswmswhlkteloiarwwdafaffafimufxzbzetkfeqjfaffaffaffafimufxzbzetkfeqjfaf...

output:

1845388242333177970
9831947454379400267
1031368185674017505
7263197708536716267
14239370791222150808
146482920919415220
17250529541921412624
16073012951843647214
14426094333257632462
9475986787147068259
17618123199330645299
7007181348027660953
7868744985222980634
24008326611725469
109704767314001231...

result:

ok 5000 lines

Test #12:

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

input:

5000 5000
rreurrrrkodwxsvtckttkrreurrrrtvjqcbspphhcmqjjadnkvdhavzhasjorreurrrrkodwxsvtckttkrreurrrrdhzorreurrrrkodwxsvtckttkrreurrrrtvjqcbspphhcmqjjadnkvdhavzhasjorreurrrrkodwxsvtckttkrreurrrrxgpkocctymfhcjougjsvimxuwczjxyhasapncenwpvkvtrmcdhkfjmndumgccngxginwyjhwexjeujrnvfaznvonweytryeeoocesoxavgaw...

output:

11585208823777493396
6508373161762025375
8952030838195753202
1744593196955201879
7361869313836500243
4211703722346758091
11507326811546869387
12152026172660216436
6502452509264613488
16456537462830488502
7769483154726766332
5049920983662723085
6208254085958990276
1561961237223372279
2581189727041718...

result:

ok 5000 lines

Test #13:

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

input:

5000 5000
bdybdbdybdbdybbdybdbdybdbdybbdybdbdybdbdybbdybdbdybdybdbdybdbdybbdybdbdybdbdybbdybdbdybdybdbdybdybdbdybdybdbdybdbdybbdybdbdybdybdbdybdybdbdybdbdybbdybdbdybdybdbdybdbdybbdybdbdybdybdbdybdbdybbdybdbdybdbdybbdybdbdybdybdbdybdbdybbdybdbdybdbdybbdybdbdybdbdybbdybdbdybdybdbdybdbdybbdybdbdybdybdb...

output:

15484750028865001809
11154229346905269019
17415778058314228645
12967502341758445430
14197547387946783600
16593119823307221414
3430123628603013461
15944735630911629097
3372966924712269006
16370170534370111687
7776152546511005126
10081736260495879969
3361043444817366723
14159037165445633566
4790222378...

result:

ok 5000 lines

Test #14:

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

input:

5000 5000
gskozovzgkcfxgrjipkmaurpgskozovzgkcfxuetjsdskistgkrkxbvpwljcjmnamkcdqmeteslgskozovzgkcfxgrjipkmaurpgskozovzgkcfxgskozovzgkcfxgrjipkmaurpgskozovzgkcfxuetjsdskistgkrkgskozovzgkcfxgrjipkmaurpgskozovzgkcfxuetjsdskistgkrkxbvpwljcjmnamkcdqmeteslgskozovzgkcfxgrjipkmaurpgskozovzgkcfxgskozovzgkcfxg...

output:

5804930040756324744
15650208817097681461
11355021187259627510
6741010156229702848
11225541410427015147
1272653894362217625
8025793205090026227
17985669688971641284
17805739950886098400
15447039299473890938
13822612697353510946
16409494890413019301
10397340813113479673
11748441386197961568
1796390231...

result:

ok 5000 lines

Subtask #3:

score: 12
Accepted

Dependency #2:

100%
Accepted

Test #15:

score: 12
Accepted
time: 152ms
memory: 30668kb

input:

5000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5845120425902525283
8990351971173725430
14941690660751686216
784971306663465014
14729108738538674226
9552307739797797498
3551599368844499432
3212787150504387790
8594382131237834529
16887368685328314652
5586192237324217034
12381470524748547090
1961055982585971300
13257376816999825159
3385756250295802...

result:

ok 100000 lines

Test #16:

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

input:

5000 100000
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszsz...

output:

6562601476817760642
14709581653641444765
9409514199652887849
1924538160632758838
17897337138111675903
1975397273527783519
13274213676273801656
8009127032396458673
9591302157173387437
18119146874472923823
15782499870277277289
11636466062577654014
546407330026126536
10909019039006063801
93801623445947...

result:

ok 100000 lines

Test #17:

score: 0
Accepted
time: 144ms
memory: 33844kb

input:

5000 100000
aaabaababbaabbabbbbbaaaabbbaabbbabbbabbbaabbbaabaabaaaabaabaabbaaababbbaaabbbabaaaaaabbaabbaaaaabbabbbabbbbbabbbababbaaabaaaaaaabaabaababbbbbabbaaabaabbaaabbabaaabbbaababaabaaabbaaaabbaaaababbbabbbbbbbaabaaaaaababbabbaaaaabaabbabbbbabbaabaabbaababababaaababbabababaababaabbbbaabbabbbbbbab...

output:

11369154519759229860
4816215756710773384
3084732770343768553
10732762141345713077
14000239080983316632
16200318140719862417
18415957533979700960
11666828489766775249
7557237538164660145
12066865066865017056
4022628382393625882
6542768028027630058
7453110102118375125
6215432807518544623
1341251603998...

result:

ok 100000 lines

Test #18:

score: 0
Accepted
time: 131ms
memory: 27236kb

input:

5000 100000
ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

12902464409189323146
2112106874663835270
17874290669032515261
17889078556270410717
1153359439408633103
17496184927378147549
4218582814297155576
12182030755254116397
2311499738865929178
12069095198538404628
11646473706806926093
13424856046086967932
13546170125890126237
9125301078493922531
68650470543...

result:

ok 100000 lines

Test #19:

score: 0
Accepted
time: 137ms
memory: 30480kb

input:

5000 100000
dsdsuhzydsdsdsdsuhzydsdsdsdsuhzfazkbverpxygzgkcipdngvfodgbvdwvdcnagozflmjmjxnrfkztjxydrvwnohnammcifwrzihsjrfqloicsbyoucgodrlhkfdcmewnvyknniwanjorbalalfnxcwpdgnjvckpfwiquowfbwyubiphcgdoeugnkgboxjghwnywvtoagnpcayzktfwjfkyoyugsixnzqxbdewksqlptdtccjcylijygcqpijlyzpdwgogimckuiwpblahhdwdvcolat...

output:

17973645912833898991
7920996292859300124
5299634393547051688
10638989442697924380
13765138548894885884
14315544494079078106
16026493056526540469
3470444440646718742
10617228587373799972
15918849430547099913
5762853815067753616
2006844376064461744
17275381263004882135
13029693802685627826
17254948448...

result:

ok 100000 lines

Test #20:

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

input:

5000 100000
juptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjuptjujuptjujuptjujuptjjuptjujuptjujuptjujuptjjuptjup...

output:

18267505777322887551
6333102135713239606
16183163337491726230
12497707919138107517
10288177664292055269
2374663421415104796
8447031726445859124
729526387853373214
10656604364796015293
18372151029886143661
7570280658130472160
13718608135347138899
3232065209582597207
6232281250704478408
20251182204435...

result:

ok 100000 lines

Test #21:

score: 0
Accepted
time: 147ms
memory: 35148kb

input:

5000 100000
mkubtkmkubmkubtkmkubmmkubtkmkubmkubtkmkubmmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubtkmkubmkubtkmkubmkubtkmkumkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubmkubtkmkubtkmkubmkubtkmkubmmkubtkmkubmkubtkmkubmmkubtkm...

output:

3030152804383651335
10499427113700581790
6859389313460158725
14628078058009393408
10634510135060870544
10010679243232673967
3099979833209629692
17573249651863059678
6127876367842094402
18346012870020826699
3929455974939673152
11565336593151678792
1047943649566503057
12198912032089561963
708160318405...

result:

ok 100000 lines

Subtask #4:

score: 6
Accepted

Test #22:

score: 6
Accepted
time: 172ms
memory: 102744kb

input:

100000 100000
zbbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:

16102224067619618967
2409962914769200003
427496158535942638
17668679206267169316
9612725428377010375
16283030984784184667
14966758574838045581
8108029333542434517
5821899279772898061
7354415533246368927
15016230232022193055
9072126619623269970
5490256818353051548
432088324301719512
13681741566473101...

result:

ok 100000 lines

Test #23:

score: 0
Accepted
time: 164ms
memory: 94348kb

input:

100000 100000
zsyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysysyysyysysyysyysysyysysyysyysysyysy...

output:

4559870725517531243
7294838067589907718
11611591353940805930
6570123277626119382
7422995984298182834
5907659314847245750
16910510485299347733
4264602948914788684
13190214217087942183
6600183534290302450
18342681242733610030
11565497126186922166
17128453730139037795
1670830382187028213
18164994643596...

result:

ok 100000 lines

Test #24:

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

input:

100000 100000
zoooooooollexlwockjmmpcsmrmxbcsxiopbhrsgmuffubpextcneqsmtouhuovwmosufyvtciwaiqfgxdjgebcnwbeyyyascjixpskyeyoecigpydkqrssvcwcuirkwyxxbcfgjdorrrgdghdooooooooofnkxriqwewxjgitnhfrykdhcrpbgmcnqujvlugcougvywjyjknbcfqdohyxidpswedsqodaqavibkmrykeiqfmoyavdcctpjvqomwmhjysbynqskjvprebydvglxmnqsvxy...

output:

812998614822431625
1250302312590066903
0
17068288240276554944
8822011249064016718
5154878686056167322
16634251694703169315
7627132526351165031
17489820411768677459
1612901206518396247
9557606214238964493
8125053178366415794
6923591044772654970
16010694286126551160
0
11810757301219826743
180907391938...

result:

ok 100000 lines

Subtask #5:

score: 0
Dangerous Syscalls

Dependency #4:

100%
Accepted

Test #25:

score: 16
Accepted
time: 191ms
memory: 106120kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

15893638524428831028
10131593916133042820
10131593916133042820
1813611689029665142
15893638524428831028
10131593916133042820
1813611689029665142
10131593916133042820
9834492063345021236
9834492063345021236
15893638524428831028
9834492063345021236
9834492063345021236
10131593916133042820
158936385244...

result:

ok 100000 lines

Test #26:

score: -16
Dangerous Syscalls

input:

100000 100000
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzsz...

output:


result:


Subtask #6:

score: 21
Accepted

Dependency #2:

100%
Accepted

Test #32:

score: 21
Accepted
time: 300ms
memory: 64160kb

input:

50000 50000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

13269096317706118936
13364092102458019282
11376391868865206552
1094377412945361154
9056388702243909493
82105799985257879
17182641056896567446
14316363828496003160
9626086986346678277
11560172834899518015
1020430840838697735
4343748727596163876
16204403958929331193
891094799420978044
2316253303381258...

result:

ok 50000 lines

Test #33:

score: 0
Accepted
time: 385ms
memory: 52172kb

input:

50000 50000
zszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszszzszzszszzszzszszzszszzszzszszzszsz...

output:

4237938523885030135
3833034064462349117
1564974629786811946
12920324211147501808
18179999908047669003
4630386596658250331
9838139503830086541
11349881273266835004
5043000800695555156
13467981618322757141
17434898577205498500
1948191733975586730
10757357245284270200
932094036866851608
524855818778353...

result:

ok 50000 lines

Test #34:

score: 0
Accepted
time: 645ms
memory: 72436kb

input:

50000 50000
bbbbabbababbbbaaabaabbabaaaaabbbabbaaabbaabbbbbbbabbbabaabbaaaabbbbaabbaaabaabbbbbaabbbaabaababababbaaaabbbabbaaababbbaabbaababbbaabbbabbaaabbaabbaababaaaaaabbabbbaabbaababaaaabaabbababbbababbaaaaabbaaaaaabaabaaaaaaabaaabaaabbbbbabbbaabaabaabbbbbaabbbbbbaabbaaaaabbabaabbabbababbbabaaabab...

output:

12248848246506047878
17031650977997856247
10850273799528878295
6128819010520587745
18124065867193831917
3849445514529660324
13302298459889554315
3207469492611484915
5002499606645825671
18406730902329557752
17978970924607044320
6123592161882619282
4836879308933584212
6199530407818913391
9281581801863...

result:

ok 50000 lines

Test #35:

score: 0
Accepted
time: 545ms
memory: 70232kb

input:

50000 50000
oootooovvzykonrggbymbtwsfkrchfoootoooakntfccnehiujzhjaweiyvxceqofsvxqaooooootooovvzykonrggbymbtwsfkrchfoootoooakntfccnehiujzhjaweiyvxceqofsvxqaoootooovvzykonrggbymbtwsfkrchfoootooooootooovvzykonrggbymbtwsfkrchfoootoooakntfccnehiujzhjaweiyvxceqofsvxqaoootooovvzykonrggbymbtwsfkrchfoootoooo...

output:

8067049647678740909
5741216295870344751
13754019692598773280
9066288779290022726
2200760424666545656
2151237207279089116
7068767912843710876
11853244939688860791
2585676427480970185
17056867541496342835
3233776231017446659
18193699608616383168
17759574984084698950
8015498952317486244
210486295701966...

result:

ok 50000 lines

Test #36:

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

input:

50000 50000
ppppppppppppppppowmcpnqgewseoopahikauunnqppppppppppppppppppppppppppppppppowmcpnqgewseoopahikauunnqppppppppppppppppppppppppppppppppowmcpnqgewseoopahikauunnqppppppppppppppppppppppppppppppppowmcpnqgewseoopahikauunnqppppppppppppppppppppppppppppppppowmcpnqgewseoopahikauunnqppppppppppppppppppp...

output:

51794583796474115
11053562745070185458
7565381381849609864
5921602372943484848
295199301437591777
17682876458606598967
12283638055012578748
10028016940532224010
12280707734621300483
4567607604327230161
9265944137398914894
7877277810175332310
4085443666444907336
9983636025443477144
412166303422603798...

result:

ok 50000 lines

Test #37:

score: 0
Accepted
time: 655ms
memory: 70760kb

input:

50000 50000
kbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkfkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkfkbaqkkbaqkfkbaqkkbaqkfkbaqkkbaqkfkb...

output:

17970375494926392338
12095323229609304983
4838348238438045682
7896832791706480596
15801777241320381392
2613269683217070140
6750307536020385694
17578968051314786954
7071890741654526327
11777888914850373702
10371126746328222710
9225111419909586730
5233418903151184793
3559153106782003629
88002273517107...

result:

ok 50000 lines

Test #38:

score: 0
Accepted
time: 561ms
memory: 70396kb

input:

50000 50000
wczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlwczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlmikhbatynoykqnlpvgrvcmhwwczchwwczchwlwczchwlmikhbatynoykqnlpvgrvcwczchwlmikhbatynoykqnlpv...

output:

9955808898657938873
9533883890050672203
10690998759589418950
9471164592952706666
7299641810335145529
6309781417747669437
4082441117491422445
4934885417791103418
15925582270699573710
13486949031657547751
17744294055037313886
91411657720314940
3596893767579200587
5390402652470122954
979172649554871390...

result:

ok 50000 lines

Test #39:

score: 0
Accepted
time: 584ms
memory: 71184kb

input:

50000 50000
liltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsijecxwfcrdrkyliltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsijecxwfcrdrkyliltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsijecxwfcrdrkybnfbfhmhjuogkofjslilliltqjsi...

output:

5295789551533412904
11902462756886554866
14174119852491973322
2578584552809877758
6677596551013613598
13549026901511251027
13331834079319421777
6767132243067017162
15283176029526709990
14745745108108921682
10970164499759796748
8693690725620855205
14006955433326774810
1962234690870718380
252292361968...

result:

ok 50000 lines

Test #40:

score: 0
Accepted
time: 479ms
memory: 68888kb

input:

50000 50000
kfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfiykfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfiykfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfiyzelyfkkfiyzelyfkfkfiyzelyfkfkfidfsnttbzbzhdzbsefmy...

output:

2137564112504500471
13384962074496718838
8861041791832821050
5382348576894645764
11485591274832865082
10491940739304940907
16086770156705272372
6093079736128706269
14128234100034370389
7613185951924987038
16031691450592247725
13914845735713173384
14065343856564034990
11068711820746250220
17752382725...

result:

ok 50000 lines

Test #41:

score: 0
Accepted
time: 392ms
memory: 61496kb

input:

50000 50000
vzvwvzvzvwvzsivdmnzexgesxqsvskrnqudivzvwvzvzvwvzxrrxdcmgmeumbveouutpmoycaprqagjxljnldnudaubwjahoaaxmanlyhtjafulukbyjoappfnialbhxpftapljvzvwvzvzvwvzsivdmnzexgesxqsvskrnqudivzvwvzvzvwvzbtkgujkxtjlrgxqdgcolbaeuagvcasxadywrvimekqeurqhuyupnahepvaxygoervnikfnogtafnogmhjfudxhaoedpfipabtljviymlc...

output:

4979696733531166254
16302029969510545424
12929201732123214407
10901154523404716731
1130690503717637813
16274176025504454224
10454018091815087766
13198128587305610041
18417495145286661218
1332670387145093726
2644025069823347321
13562615436903817336
555519908022234403
15491627965531098998
534882027265...

result:

ok 50000 lines

Subtask #7:

score: 0
Skipped

Dependency #3:

100%
Accepted

Dependency #5:

0%