QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#593913	#4631. Interesting String Problem	ucup-team3161^#	AC ✓	1478ms	345976kb	C++14	2.3kb	2024-09-27 16:55:55	2024-09-27 16:55:57

Judging History

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

[2024-09-27 16:55:57]
评测

测评结果：AC
用时：1478ms
内存：345976kb

查看

[2024-09-27 16:55:55]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define eb emplace_back
#define fi first
#define se second
#define mid ((l+r)/2)
const int N=1e6+5,M=2e7+5;
int n,m,tp,sz[N],dfnl[N],dfnr[N],o[N],p[N],w[N];ll s;
pair<ll,int> z[N];char a[N];
int nw,cntp;bool tg[N];vector<int> e[N];
struct Point {int len,link,ch[26];}pt[N];
int cnts,rt[N];struct Seg {int vl,ch[2];}sg[M];
void ext(int vl)
{
	int p=nw,p1,t;pt[nw=++cntp].len=pt[p].len+1;tg[nw]=1;
	while(p && !pt[p].ch[vl]) pt[p].ch[vl]=nw,p=pt[p].link;
	if(!p) {pt[nw].link=1;return;}p1=pt[p].ch[vl];
	if(pt[p1].len==pt[p].len+1) {pt[nw].link=p1;return;}
	pt[t=++cntp]=pt[p1];pt[t].len=pt[p].len+1;pt[nw].link=pt[p1].link=t;
	while(p && pt[p].ch[vl]==p1) pt[p].ch[vl]=t,p=pt[p].link;
}
void dfs(int u)
{
	if(tg[u]) p[u]=n-pt[u].len+1,sz[u]=1;
	for(auto v:e[u]) dfs(v),sz[u]+=sz[v],p[u]=p[v];
	w[u]=a[p[u]+pt[pt[u].link].len];
}
void dfs1(int u)
{
	int l=pt[pt[u].link].len+1,r=pt[u].len;
	o[dfnl[u]=++dfnl[0]]=u;s+=1ll*(l+r)*(r-l+1)/2*sz[u];z[++tp]={s,u};
	for(auto v:e[u]) dfs1(v);dfnr[u]=dfnl[0];
}
void upd(int p,int &p1,int l,int r,int x)
{
	sg[p1=++cnts]=sg[p];++sg[p1].vl;if(l==r) return;
	if(x<=mid) upd(sg[p].ch[0],sg[p1].ch[0],l,mid,x);
	else upd(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x);
}
int qry(int p,int p1,int l,int r,int x)
{
	if(l==r) return l;int t=sg[sg[p].ch[0]].vl-sg[sg[p1].ch[0]].vl;
	if(x<=t) return qry(sg[p].ch[0],sg[p1].ch[0],l,mid,x);
	return qry(sg[p].ch[1],sg[p1].ch[1],mid+1,r,x-t);
}
int main()
{
	scanf("%s %d",a+1,&m);n=strlen(a+1);nw=cntp=1;
	for(int i=n;i;--i) ext(a[i]-'a');
	for(int i=2;i<=cntp;++i) e[pt[i].link].eb(i);dfs(1);
	for(int i=1;i<=cntp;++i)
		sort(e[i].begin(),e[i].end(),[](int x,int y) {return w[x]<w[y];});
	dfs1(1);
	for(int i=1,t;i<=cntp;++i)
	{
		t=tg[o[i]]?n-pt[o[i]].len+1:0;
		if(t) upd(rt[i-1],rt[i],1,n,t);else rt[i]=rt[i-1];
	}
	while(m--)
	{
		int u,l,r,l1,r1;ll x;scanf("%lld",&x);
		int t=lower_bound(z+1,z+tp+1,make_pair(x,0))-z;
		u=z[t].se;x-=z[t-1].fi;l=l1=pt[pt[u].link].len+1;r=r1=pt[u].len;
		while(l1<=r1)
		{
			int mid1=(l1+r1)/2;
			if(x<=1ll*(l+mid1)*(mid1-l+1)/2*sz[u]) r1=mid1-1;else l1=mid1+1;
		}
		x-=1ll*(l+r1)*(r1-l+1)/2*sz[u];
		printf("%lld\n",qry(rt[dfnr[u]],rt[dfnl[u]-1],1,n,(x-1)/l1+1)+(x-1)%l1);
	}
	return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 3ms

memory: 40780kb

input:

pbpbppb
3
1
2
3

output:

2
4
7

result:

ok 3 lines

Test #2:

score: 0

Accepted

time: 0ms

memory: 40616kb

input:

potatop
3
6
30
60

output:

6
3
4

result:

ok 3 lines

Test #3:

score: 0

Accepted

time: 132ms

memory: 43132kb

input:

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

result:

ok 500000 lines

Test #4:

score: 0

Accepted

time: 172ms

memory: 41064kb

input:

gtgggtgttgggggtgtgggtgttggtttggggtggtgtgggttggtggggtgggttgttggttgggtttggggtgttgggggtgggttttggttgttggtggggttgttggtggtggggtgggttttgggttggtgggtgggtggttgtgttggttttttttgttgggtttgggtgttgttgtggtgggttttggttggggtgttggttggtgtggtgtgggttttggttttttgtttgtggtggtgttttgtttttggtggggtgtttgttgttttggggttggggtgggggttgtgg...

output:

result:

ok 500000 lines

Test #5:

score: 0

Accepted

time: 180ms

memory: 41012kb

input:

uuppuppuspusupspsuspsusssuupspppuuuusupspsssssusppsppsppsppsupuuupsssussupspsupsusssppsuuppspsuuspuppssppssusuussuuuupsspupssupuuppppsspuuspsupsususussupuppuuusspsuupppspspuupuppuuspssususpsususpsspsspssuuupuppppsupusupppsppspsuuusspupuspuspsusspsuspuspssuupuupsssupupppspppupsuspusppssusspspsuuuspsp...

output:

result:

ok 500000 lines

Test #6:

score: 0

Accepted

time: 172ms

memory: 43144kb

input:

vqvvsvvvvqssssvxvxsvxvsvxxqsqxqvvxvqqsvvsqvvssqqxvxvqqxqxvqqsxvsqxqvvxxvsxvxxssssvqvvsxvqvvxxxsqxvxxsqssxvvxvsxsvsvvvxsxvsvsqvvvqsssvvvqxssqqqxvqqvsqqqsxqqxvvsqxqqvsxqqqqvqxxqvqvqqqvsvsvxsvssvqvqxsqqvxvqqqvqsssqxsvqvsqqxqqqqxsxxxsvsqqqxvssssxssqxsxxvxqxvqsxxxqxssxxvsxxxqqvsqxsxxxxqxvsqsvsqsqssvsxqsv...

output:

result:

ok 500000 lines

Test #7:

score: 0

Accepted

time: 166ms

memory: 40948kb

input:

hcccjchdjcccjchhhdjnjdhdhdhjhjnhdcjdjjdddchchdhnhnddjdccdchcjddhcdhhcnhcjjjdjcjndcchcjnnddhdjhdddjnncnjdchhhdjcjhdjjdcjdncdcccncdcncndcjcchdhhjnhjdjnnddcnjnhcdhdnhnhjdjjjdhcdhhdjdjcdchcndcndnddjdnndjhdnndnhcdcnnchdcjndnhnnhhnddcjjndjnnhnccjhjjdhdhcndcjhjhcdccncjndhcdjndcdndnjdjhddchccdnhjnnchhhhhhjn...

output:

result:

ok 500000 lines

Test #8:

score: 0

Accepted

time: 171ms

memory: 42988kb

input:

cjggyjgjcffcgczjyjzjjzjgzcyzjczjffycjzccjycyjjyfyfzcjggggfcygcygjcjczcyzjffffyfzzzfzzgjyfccggzzgfygyzgcjgzfyczyyjggfyjyzjjjzyfzzzffcgygjzjjzfgzjfyjgjycfgygfgzcyfzjjjzfgfjjgjfyyzyfcfccfjgyzczczzfzgjgjzyfgzygfgjzjcyyjzyffyczzfjfgzyycygfcccyzzjcfcfccgffyjygcgfycyjjjfjjcjggjcfgcfgfjjcgzjzyffyccjfzycjggy...

output:

result:

ok 500000 lines

Test #9:

score: 0

Accepted

time: 171ms

memory: 45116kb

input:

illulituiuyifyufffilyuilnynliiftnyinunltinnltluiltinuttuffiffitfylttiiltnuuiflfiuiuntiniluiinffyiylunnufitlltnntnufuiltnyuyunuflfilufilluinllttinntliufyytnifytfuunltlnffiiyluuifyftnyifnntfilliyyiunfiffyiytnytlnuilinfynunttnyttnuttiiittnntntytittiyyniiutfffynfuffiiilfyulffynnufuuuyiffuyyyfuitflntlnni...

output:

result:

ok 500000 lines

Test #10:

score: 0

Accepted

time: 172ms

memory: 40968kb

input:

aykyaaucykauxckywnaxwwawxycxyanaayckkxuxccawukxkuaxnyxuxcxucynkkknkuuxwwxauyywxakkwwuwxkyuncuunxwkaxwnkawkxxxykwuauccyaanunkxawwxwckukykcuuxwnwxwcynnukwucukkwkayuyakuuxknaxknnkakkukukxucxkcnxcaxywaawuxaaxayknxwwyxkncnuwkuuxwywxxayxkukwxawnakyuxnkwkwaucxkknxxackuuyynkyccuucnuknynnyyucxnuxwwckwykawxyw...

output:

result:

ok 500000 lines

Test #11:

score: 0

Accepted

time: 182ms

memory: 43168kb

input:

iyaaobwiwaawywiovmaabvwomwmmobwvowoywiawmimimfvyyywvimvofwwmvfwfowbyombmmmbboooobvmfvfoawiwymfoomiwivyvobfwivmfiayyofvmvammwmbfowifmmoaifwaiovywbfymifmibobiawoiiiabfwomwiayobwyvvommafabmmmmiiibiwvbbmommbofbyvmvfwiowaovyyoywmwbyfmmbmvyimwoiivmmomyvbmommoavmbbiimovfiafwiaffbbffiymvvoiwwywowaoofayyafif...

output:

result:

ok 500000 lines

Test #12:

score: 0

Accepted

time: 165ms

memory: 43080kb

input:

vbvvddssmuqqsybsyygvqviduqbgiviqbbsqgisgvyguiqyssqiyuiumsbuiyqgqivqvbysvdmuigvsviubimbidbsygqdgsgdgqbdggidbbyuuddsdsvyivgddyyudmsuvgvdbmvdiuyyibuqdvvgqsuqmisubyqiudgyqmsmiysyussygbvyvsivimqqmviisvvbqsbqsgyiggbbimiqsmisiidqdusvivqvyibvvgmmbqsudigiiqdmdbubvbvusbyygydbqmdggvmqmdbdudidsymqbqbuiubmvqgduv...

output:

result:

ok 500000 lines

Test #13:

score: 0

Accepted

time: 176ms

memory: 40992kb

input:

btcuswtwttuulltfdllcdcyccdqwyfbqlyqbqwuqqquccqqluqqsuswfbqtcbdtldfylsllfbddtbdcbwdbcdwwbqcdtcudqdcylwstttduddbubwysydqqsyswwqfcutyyclyqlqfbwscycwttdfsldfssfqftydcftldwfuubyfqfscfwbstcylblqftsqbdybydbtcbfqlcqtssbtulyfstuytdwcbbylqutqlcfwtuwwqldycusqwwyluqwwubfyllqcqfstcufwlwulcbbwdsudfltqtdcsclyylywt...

output:

result:

ok 500000 lines

Test #14:

score: 0

Accepted

time: 175ms

memory: 43040kb

input:

sblrorbgldylcdrxooszdrxciizgrlgcxrobrldirgxdxgcoscszlzlydyllzxdzirsxscsozrglbdgbxbgdbsxorlxxcgxizdxgoxocicxdiislosrxocxgszxixczrbllisdbgcsyzxlliidzdxdsoyrbcizcblrdxillybszbycxyicdbcssdlsiixizrlgobzoizcdrdrzlrigblziyrzrooczdiogdodbsyslcdcgrzycoiosxblixizdsglxdrisszcgisilbxgobiygzdiysxxydcxxrlbcrgzdiy...

output:

result:

ok 500000 lines

Test #15:

score: 0

Accepted

time: 167ms

memory: 41040kb

input:

zcfkrrjhbjkzrafjbfvcbhfckpkkgsrvjcjkhcrrsazcjcvbajhpaazapasacszskzzbsbpszhfrpjgjhgpaappvzhjrgrfzzbszkzaccksjhsjczbvhkpzzkarkjzvzvzcbvfshazvpfbzcpkfrjfbachksgzrsagkgzvvavzkppbvjcvjgzavgvfjjvhgczzvhfhcrcjsskzpvrzvbgzbgzrghgkjgaafghgjhcvbgvzrbhjrfjsakbrbscjfpkcsbhjzfkrjpkrpsgkahfkjrakzzjjvcaphkjvhfzkgh...

output:

result:

ok 500000 lines

Test #16:

score: 0

Accepted

time: 166ms

memory: 41104kb

input:

nctmfuwtjtktmkwlfpmjuwnklufnftrjuwpcjrntuwpkwpphwckfqrmqtkcmltmhufcmjtmhtuqfhclnnluuwpjqwmtpwkppfnclcjpchkkmwnutrhwnpnmhcuctffkcpflqnjrnjnfkhwmnmcpwrrttpnwcfnqrjlqmtkncfcqjufkjctlwmhnfcnhpnmmktnjphpmnqwcjqmmfjukllwurnccmqhquhrfumqlmtmthchuphpullnmmthpwrhwlkpujlkphnftpnhtnlkmunfnpqjfjpppnmmqtfjwnfhcc...

output:

result:

ok 500000 lines

Test #17:

score: 0

Accepted

time: 172ms

memory: 43024kb

input:

qpwnfmpwfufwiieehpfuwuepigxfuevgepiuihmwformmurfrxueurfvnxrimhihxfofonqhpreffrnhnefhqxwopiupouqqogomoohienioworxfwugrigehxixiifefrgrfgqvorngnvqwwfxeouiegxfohivmhqvqiihmoxwgnughgewmxpuqfrpvrvpmureumnxqehnwnqrgghwwieopxmnpmvimfqvmmhviepxinropffvngwhourxguvhuripfpniugevigrgmonvqieeqxpiqwvfmxvmevhmhhiuw...

output:

result:

ok 500000 lines

Test #18:

score: 0

Accepted

time: 181ms

memory: 42984kb

input:

tgaxtbbpxabtqufqkucxqzhqraobozqpiftzbafxhcbuqhuiifhtrrpihobxxcuttfqhpkrzkbpotaghbqtupoqpoczahtpczbxikrioxbpxctpxbgocqbahqobitipfhoqragtqrcgcihgotichpuzcqkoobhhgtutihrpgxkbqxohgcthffhcfopfapbphqfapgzqgahupfagzzhpopkbgtfcqafpubqhzizzqtgqpkopioxbzahihrqiaappxzgzxxrccxpiafpbxiffoquhuibbchxukziqcfcfopzxg...

output:

result:

ok 500000 lines

Test #19:

score: 0

Accepted

time: 167ms

memory: 41044kb

input:

wwtjqqtttozlzdsjwfkojmsvlofvkhvrvdzlmwzkshqlfzmgkzqklkjhztvjwgtmxvrglwmvkottxsftmwmsvgqmgqhrsszwdkldjkvtlvtzlvgfzwvszqsohkdgflgvlfgkmxmfvosxhsjsomxmsgtozwrogkrffgqwmtlljwsqxshgtkmdkwrktdzfwxljjvosxjqogxmrvomqzoqkrkvtlmgqfgjzfsrfwdrwzskdtjlsodzhwxxfdwjljzoofdqtdhjwolktjgdjwxzhtxrdstrrrwsgdmwgorldllho...

output:

result:

ok 500000 lines

Test #20:

score: 0

Accepted

time: 166ms

memory: 43024kb

input:

iadnxnxelwnjiiwxcteaxpcmphvwphjidjpnwimahcjtmvizihxhsnammddtzevjvoimnhlxjnmjwihaxcpepneacwpmjeevtpvsdzsmaztzclaeoxdntaoazxllsemascencxopanjaxdcntipxedxzjdeipidwmzovesvtoijshcwcixjievvdoadilojazolcnldahxiswppmdjzwlmnanmcpvewjhihdmstixstsijlwotlpmlpsxlevzainmznatvzllihtjpnpxlnhedmpwlwhvxitatjcniapoije...

output:

result:

ok 500000 lines

Test #21:

score: 0

Accepted

time: 165ms

memory: 41064kb

input:

yqoopvwnfaubnvwpybhpbjoonfiqbvjbuyhyvvbjusiniphqcbuynkvheonvvhkkfbycuknmmvawjefuwyjppccakqjcfaoeiwvfhyipwhhkswhswjoaubvhuqoncfwemnqnucpusscahavbijffcbffqnfafamvmmoschhyenfnhwfouipmwebfinyyqjhimwopjbhypsuqwynyjbocjysubhbyshjnoeefcwyhpaiihnbupoeebickkqewkwnjiwkhbyioupqmkychimpopsonuvwmwkffvqpcnbmhqhmp...

output:

result:

ok 500000 lines

Test #22:

score: 0

Accepted

time: 170ms

memory: 43024kb

input:

nlofuytixdmtwouugdfosniyfodlpmlmftlewdsptcecnlynddneysyceudxcismpluopzexnpzttxppfzonmgpmnuemiyfzfxzegbvsxziwezwmnleyogxpcdvivynstweupygspivlcpomnbfusgiudiollwlvtxsdswcnupxzositewmnwnzcwmptisdvtbsiwtupoppximyfvuiytfyvfcpsocelpevcvntultngnmgiluucsixbxbzgyecuetzecbndlgbvteptfbscnonextldlgbeybimcczmugdn...

output:

result:

ok 500000 lines

Test #23:

score: 0

Accepted

time: 174ms

memory: 41048kb

input:

evgsxyszizjvkayssyjimmvexcignjtcgpqztggfgjiqccnjugafqiyafspiegpmanhgevghxxasigntxgvfuvgmzzxfgfvogzggfqekkszfauhpjezffvtktkxyxcktzfsvueokzsmpfiiyauxeuuecokqteyaajmnyzygnnmzgshnyopfiysxuzoezfzvaonhvogsxkqmcspmoeeiyqkkfmcyieegyhgsnqxqvahyegohspkyecujsisixkuvymivkzjaqopeksnshsegyhemaqityucjhegjycghukpii...

output:

result:

ok 500000 lines

Test #24:

score: 0

Accepted

time: 171ms

memory: 43104kb

input:

ovoojjlcfwuqpcneuhknkcvqkiuotuwfsczcpokkryumycqebwzpwjehopuyfiwihovecyqewqzuuerieszwutuwfjtkznsenirjthcptrjribfkeihyusrufntjjtsecrpqrubclfooykroczvhqywpnfwkjyjmwmpnyciskmumzsrsjspqqusefmoofvoszfizrrcnjqnbvzreemesrvorkmhitwzejmrhcikscosymjvcmjecmuzmsthkqwycwpbouineiflnqucyohriqmkykhflqrmpijqlwjfmyttf...

output:

result:

ok 500000 lines

Test #25:

score: 0

Accepted

time: 171ms

memory: 43104kb

input:

nvhhpnuysrbeuylwdgivwbsiegwrhbhbxybyludoaqewloavndbxenhaionhlyonwqxtvddyaftayskertyufnhwxklhousuvnatorulwxrkkbdrtfxtdrtunygukdlccfldgducurcfsfvxdbqahkpnivukfwqncpprbkxlouwcbqypcqeqtsbxghhiairctwordktkoancfgsckdvqsrcnkpsbecoctuulyrapqiwrsnrcoqdxrpyrhdcxsvfxfekslxlprssvtrwsalgyhthvdnhvesfeucdccirfirkq...

output:

result:

ok 500000 lines

Test #26:

score: 0

Accepted

time: 170ms

memory: 42968kb

input:

qnclwkavcnrqyegjasqqsrjsnsybneliwmocgacduivkussloxklajrloagadudikenalwmozevggcarbikgvaamjelqateowqsjhxqsgamabjtignibxidhxyxxxdzdiottlgeoujgihlndxlvoeoincmtooouveahrttnznuswogsudngbdynsrlgkwmbdducdquorudwqkatwybezekxwxvdwkngxoaakcowkwcebvmdgudguogwbstzewdgikohtdsujwngxcehgtorzcxlyxhtabrmojqtdcwxribvd...

output:

result:

ok 500000 lines

Test #27:

score: 0

Accepted

time: 171ms

memory: 43116kb

input:

wyegkiddibdhattrwgvqqtznwnqteeafiyenwsislkaqhhkuhrkkadcmfkrookocynirclwasnpcypxrxsaonsfyedmtkmyeugcuaureyrotbfchclwfdnwobktrkixmdowoucsfkwluwxslozpxbafqietyatqgedpvxibqseobffwzwxnroifyfrqnnmgmrulsscyztwybupzuavfuyuvqxwkgtnqxrfoizzrwtaxiynkszmzuzrzitermqcarybxpwftiogdakopapwbmahtzdesnwloydxyydyuomnyt...

output:

result:

ok 500000 lines

Test #28:

score: 0

Accepted

time: 170ms

memory: 40916kb

input:

mwmbcwtvwdrdwvmyeyxufotofxicsyxfuqvvgsmdmgaxgnefqcqmzdmxbkyaknbiiyxrvzedyadwzhrhdjnfxgscujrucnbejcygcccyqmeywhducissvvvvemkunevwdoebknnxtowyqwhpzlqpobqavbhtstrmriruxgkjrgoxbtosifmswgaseayewttdnqpcusxzjlevymiphhkbbmfrdjfucckzgphdaefgkumbmwyoytgiefibzqkbrcyneetwzxiikxwscugrlcezesjmtspioelcetkebqugxozz...

output:

result:

ok 500000 lines

Test #29:

score: 0

Accepted

time: 616ms

memory: 281208kb

input:

llllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll...

output:

result:

ok 500000 lines

Test #30:

score: 0

Accepted

time: 1301ms

memory: 264988kb

input:

osoossooosoooossssssssosossoossoooosoosoosossoosoosssosossososssossossssssoooosossoossoosssosssssossoossososoososooooososoosooosssoooosssoosossoooosooooososssssossosssssossoosoooossoooosooooossssossosoooosssssossooosssosossossoososoosssoosssoossoosooosoossooosooossosssoooossossoooossoosoososssoosooo...

output:

result:

ok 500000 lines

Test #31:

score: 0

Accepted

time: 1478ms

memory: 296648kb

input:

aaexeaxxxxxxaxexaaaaxxxaaxeaxeaexaeaaxeaxaexeeaaeeaaxxeexaxaaexxeaxxxaaxaxxexeeeaaxxaaxeaeaaaaaexaeaaaxexeaaexeaaxxaeaexxeaaxxxaexeaaexxeeeeaeaxaeeaeeeexeaaxaexaaxexexxexaeeaeaaaxaaexxxaaexxeeexexxaexexaaaxaaxxexxxaaaaxxexxxxeeeaaxxxxxaxxexaxxxexeeexaexxeaeaxxxexaaeeaaxexaxxxaeeaaxxaaaeeaxaxeaeeaxax...

output:

result:

ok 500000 lines

Test #32:

score: 0

Accepted

time: 1341ms

memory: 265564kb

input:

rrkxkkxrxkxkxkrrrrrkkxrwrwwkxwrwwkrkwkxwkkrrrwxkxxxrkwxkkkwkwwrrrrxkrxwwrxkkkwxrxkwkkrxxwxxxkkxrwkwrxrwrrrwrwrwkrwkkkxwwrxkrkwxwkrkkkwkkxxxwrrwrrrkxwkwrkkwwrwxwxwkrrxwrxrkkwxwkkkrxxkxrxkrxrxrkwwrkxwwkxrxxrxxkwrrwrxxwkrwwrxrwkrkkwrwrxkkrwwxxrkkxkrrxrrrxkkkkkrkxkxxwrkxwrxrxkkkwxxkwwxxxkkwwkxkxkkrwrxwx...

output:

result:

ok 500000 lines

Test #33:

score: 0

Accepted

time: 1423ms

memory: 281616kb

input:

juuoouuovujuujvvovqqovqqvjvquujjoujoqjuovuuqvjuqojqqjooujoqoovjvooqvoqojjojuvoqojoujjvojvquqvoqqoujjojvjuuoqqvjjjjvovqoojoqujuoouoovujoqjuqujvuvjvvvqquovjjojjvjjqvvouojjuvoqqjjqjqujvouququvoovovqqjqqoouuuqqvoqvujovuqjvjvujououjjouuquujoovquooouuuqjjqqvuvvjvuuovjjvvuuoqvovovjjvjvujuovqjuojqjvooquojju...

output:

result:

ok 500000 lines

Test #34:

score: 0

Accepted

time: 1355ms

memory: 279464kb

input:

jprpryeyeyeqejeeqpqyeqpqpeqprqjeqqyeyjjpjeqeepqpeeqqjyyjyeprjjyrreyerqyrrjqqjrjeqjqqyqypqrreypeerrreyyjepyryrjqppyeyejqejqejypryjpqprerpejrejqqjjerpjrpjperryejyrrjjrerryrerpqrrqqprqrejqpqrrpyjyjjpryqjyerjqjperjqyrjerqqrrepyyrjyjyqqqrrerrppqqjjjpyrqeyqqrjpepryeprepyrjyryyrrrryyqqyepyppeeqyyqeqpyyjjry...

output:

result:

ok 500000 lines

Test #35:

score: 0

Accepted

time: 1381ms

memory: 275892kb

input:

fvvwwbfwfobvfzwzwfofbfzzobzfvvozyowwovwvybybvzwooyoowywvzbfowwvoozyowbwfyofzfwzvwwovzoyzywfwfzbwzfyyozozwfzvooywovwbybvyfzwyfofbfybfbvzvwzzowzboobovoozwobofbfzvbfozobzzvobvzfoowyzobwbzfozbfzyvzvvzfowybvywzwwooyfbfzbyfyfoowvybzfbbofbvfoyvybozbyoovbozwovyybfyfffbbbooowybzofzwoyzozzwfyzfyyfwofobbwffwwz...

output:

result:

ok 500000 lines

Test #36:

score: 0

Accepted

time: 1319ms

memory: 259264kb

input:

axomeyxymofxfxfyafxgmgxafoxagxoeyxxaeofaeggyfmaaeeoaooeegfexagygmyxmemmxxmxefegfmefxmgomayoxgaeaaxeyexxxeyyyxmgffaomaggegmgafeymefeyomyaxayxxxaeogxxgeeoagegeoogyxxmaeygeeaemgfxexaofxmogomomxemmymofmfomeaagayggmmmefyyfgyaaoaaxmaxxmfaafgaeeeymexggfmfegmayeamfmfmgyyoyygeoeggmmygfgymmeeymomyaeexyfygxgam...

output:

result:

ok 500000 lines

Test #37:

score: 0

Accepted

time: 1389ms

memory: 269464kb

input:

ohgyjuoggjuhuyuuuungihunnyhgsongngysgngniohoyunuujihihuuuninisgsohnuynhihoghjugshsysuisgjgyynjuuoinhsgyyugjogssuysuuynoinuysoyshjnsngonssyjiuiosjnnninuuuyoyhjosnnogusyjshhygojssgsgoignniyigooyhgoigjioyisisgjjsygygjiynshijjhsssouygyjinhnnyjugnoiioigousnjghgshshnooungjsngosgssussyisyysojigoyjnjuugsjio...

output:

result:

ok 500000 lines

Test #38:

score: 0

Accepted

time: 1336ms

memory: 269908kb

input:

znzzqlnuzqecscezsqeecmzlnlsluqzqncezzbesssqqleeuneslsssqzqqllbcesuzqsbqumnebnbqezblscbeenzlmnumenbcbnbzncmsnmbsssnqzlelqezmbcllblzzqmunbusmbneqbczsqsueueuqnbqmzeuuembnzqcmbzezbeemqqbeuzuubbueqsnlnunsmuemmznnquuebbmnmllnslqmbqzbznblbnzmbecbznbubmlumlbzcmsnnenuqecqumnbnbuzqllsqnseqnqceuncemenzmccsnqns...

output:

result:

ok 500000 lines

Test #39:

score: 0

Accepted

time: 1344ms

memory: 270076kb

input:

vbprwpkzsrwbrgrkbagkavvbawsbsbmapsbvssrpzvszwzzpawwwvbgapggarwkvggbzmzamkvszvvzgwgbvmwrwrzspvwzssrggmpvwrmawppgmvwmprbgbmkmapzzprgmwbsazgmzrgbbskababbvvzzzprzzgvbavzvkbsgwabazasskpzabargrrabrsbprmwbgbvbkgzkbmgvbazmksgzggkvvkgkzgskpvpvzvrpmaspaggbggpzzbzakkbabvgbwwbbapaabgvbggarvkgzzsvbpszawpbmrbrvgr...

output:

result:

ok 500000 lines

Test #40:

score: 0

Accepted

time: 1365ms

memory: 267968kb

input:

efesthkhtfwsnifwhewefhbkbfbnersfbdbfttidetfifdssnwhwfnthdeebdkssbebsridwnnfktnhkskhhbttsenbwbdifttwfhwitbdkeitnthefwisbinwhfsefffrrtfrkhkiksssrrenhdhiwktfkdfhrnwdeebkfrsnhstfiddstekfbdddkiwntbidndkrtetwbthednbtnsesrbesthwbfrdbfwtibirnhteewftfnwredkidstkrdffkfshtwnfrbewbbihfwkdnsiifidiidnrrikiedfindh...

output:

result:

ok 500000 lines

Test #41:

score: 0

Accepted

time: 1387ms

memory: 267832kb

input:

mnqmbhnqqvmamnbhvkqqvwhklhqqwkvwmhndwcbwlwbqcbvnlchonqlmlkmadbcoqkowbdnkmdbmhqwawhovvdkccnkmvvlovmlqnkhqclacnchlvwdaqmcwqdqwdqolkqklhowmddbcqqqhwqvvqhnnvmcwbcqnokwqbcdqddkwhvdnckdollnblowonhqwvwccklomqbcdbwcwmdmdknclwchqccklbnlwacovbbqwddaqdqmwlkqnodvkalmaaowlolbcamwcoomdnhoawaoqalwvvnncllnwvqnnlkww...

output:

result:

ok 500000 lines

Test #42:

score: 0

Accepted

time: 1385ms

memory: 270992kb

input:

fcacaelhadxkanfukzuchlddcacgthezuguuactngnfhflktekdhlehtlggulagztnzfczccufkgkgzhdcdhzcgxnexulkekdgxketufxknzkhudndddtxlaudagchcffzzkxacazngezngcfgczkhegulgfflanuenfnlulntkkdcdeckzcndalkfxzhehftcagfxnxkuecuezchxgndcnuetldnukndhlukaukhcfdkfdegenxzxkzhlxukahuxlfhzcxlfcgdazlnzuchuadlhnktdfaukaldtfckzzex...

output:

result:

ok 500000 lines

Test #43:

score: 0

Accepted

time: 1325ms

memory: 262776kb

input:

qozgnokukouobopthpptghuppnkfnkqvvopxptbotqpbfnpgbxzggthvqkwtfhzxfwzkbqpxwfkpgzzphfohpbnxgnggqxqgtxpxzkhfobutufthfwfwowpgxuguopqngvnzvufqpqgxqtwzppwntxtkqxwftwvgnowhowzbfgqbopxwouqhznntuvngopqxfgpnkkufhfuhvbpgtwpzhonzunvfqthgqzhqwzptobzhhxugzqpfzwgoxunhgwptkbtuzookohghnvvfnuhkzntzqpoqwhwguqvqffvhwzgo...

output:

result:

ok 500000 lines

Test #44:

score: 0

Accepted

time: 1383ms

memory: 274544kb

input:

ojqojambjwokomjdkuovwumdbvgxgquqjxjqvgksdomojgsvmwadwsxwavkbjokmvgsgjxxrukgdamrzzqzumaovgqwkjvgobvxazavjsqagqdxadquasvmdkdkmzjkjuqvmbxuzkkvjrbkuomkszzbwqxgzburwodxvgjzxmdzaskbqxgdmskgjdmsmjmudzworoxrdzkxauskmorromjjosoxzdskjxwrxmbjuozxjjjwuojgmkbwmakrmxrjxzbvmxamgsxxjwjszwxqskrjzrgwzksqsdgvvmzwwauzb...

output:

result:

ok 500000 lines

Test #45:

score: 0

Accepted

time: 1359ms

memory: 267608kb

input:

tsgllfklrckavrfeqxhdxklrvcltgafcbtcjxsdgxghvqsxbqlxbasfqgfjfrdtvgllbdjlegkbrxhhfcdabecjqbdqatjgbxadsglxhajlsqaffrgetxkdhderxqaxgbqkxclthssjfgllcetbelhjtfaqgxsxbqxjfhedfvhxkvxrdkcrtdrcgravhbfahhtqgqdtalvfxejlctfghkxechajxajxaxdxescjejqeaqekhgdxetatvbtxcvkxtfjjjdtrjaxevfvqkrkxbgdkrrqgkqqjkrvvcvedlbehk...

output:

result:

ok 500000 lines

Test #46:

score: 0

Accepted

time: 1298ms

memory: 262204kb

input:

tsdijottgydnpitdnpzgajpvcocosbaausnobogajtdsnpbkrganaazvzbvobzdjbcpotdtubtrozzgrjpbunscoppypandinubjibypbakvoryvjiczputvnkpsrdbacaryoapdrkobkaspjsyszznasbtirzrrrujigztgtvkatppjkcgcjazzyibtputzskoosbsnicppvbcjycosttjkviczunvnddotpynznuoipzbskdzdcztyozobnbodjjrkndjraavjtcabcszizcvojaonrrtriarnbyrjtpga...

output:

result:

ok 500000 lines

Test #47:

score: 0

Accepted

time: 1272ms

memory: 266884kb

input:

yfxbfpkayvjwsjuokxoqvbucjcjpcnbxwnkfhockguwjgufpxsvhczpnffnzaakbwwfgsjygabsyjbhjngwvgxzsusabgppofpnbpucckwzghjjyxvjooquhshqcpzsgsgnngcsuszsnvxbuzujvazqawgxyucxnzogfagsnbgnbjaxhwggzcwnyczfgazzcfusqcjpzgxwcfavxuyynvuxokvwfxqyhqhokvnkzcbvxvwgnykogznqazfgccwbzjjpkyjjczuyyovfuvpxqshfkoyfbfbfsxgzvoffghhyf...

output:

result:

ok 500000 lines

Test #48:

score: 0

Accepted

time: 1326ms

memory: 269868kb

input:

xzdaapaedchxqmapahtpccaiktyiwgdkydqbpinbgtrdtqyrglxplmlekkrrigqilbamadcykdtpnlcnxmxqzqpzlrhcxqgipigcatnldgckribeelgirernzpzlhmdinlwylrdzqhiqxkadzhzecdridxpwdelwxrylncickpxlxrxwlbwdpykztdpredqaxgyiztbrzhaqmhzztyniicrgdymkcabhqmnyihccmgytphggateitwgdhredhmipmewmhtplpkrpcrtnhbbzmrwmzebznxiyntkipqtwptld...

output:

result:

ok 500000 lines

Test #49:

score: 0

Accepted

time: 1295ms

memory: 264308kb

input:

mbnwlfjvyylmktlycvwpjakkdxmfmnvwaiakajrjwkkwuptckfawbtnjhvtfrixvuhbhdplidcipnkwcstmvlxriuxauvncadsmuakvflhbtiubkwjydiyadwkiwmvhkfjrdxluisbrsiuicdvjuwsmvlbssrijrtihwxsyxhaclhjsxbfcxklbxkfdukmspybuvlwxmsywlxvktkxiwhmturpwrhtdvkwnbtatvydjdhiwpvmhfspnkcsauuwiyffsruajppxjvtaumckashhfibjhlvfrdwbrmhjmfbaib...

output:

result:

ok 500000 lines

Test #50:

score: 0

Accepted

time: 1307ms

memory: 267012kb

input:

kroyzcijarizdgmqmuoomcoftfmgcgezyaapoytszuxirymfiqapvzmmgdcfeatmlfykyjomqmikkxslgefscajeoasgfvmrdexkmzsedzszrpgerukcxlmiivzdroygmkpyqrigkgjmmsdgmjayxtmzdjadugqskpvuttzrmpjesoczgsuctltjrqsoultpsiocrvzudkxzmivjmtzlktvdquiotkudckpxftdajqsetijjtqmxreeytgeamcyyjrrszqrifukgjloodaktezjdypsrdaxkdeeoyrfrxrxs...

output:

result:

ok 500000 lines

Test #51:

score: 0

Accepted

time: 1382ms

memory: 264116kb

input:

dhcowxwikluqulzhkiqqurrwbmjhvjmwpaciazfudvwpqbauobxhjcelftuvcdghtxxbvikfjuhagacreuqdwefjtcicmzbivhtbjgmwzjumuzqrmlizvbcilcpombcipqpzpvgobqefjxqfxwikcgefkkdizorophddhoidevoeupabutckeltvlatckvuojergmdepdeajvofubfgoucqzhpivqfxjgllzbxawfhmjleezdqkiquipmiwmmfuaetjzccxpapvgzcfbzvvkafdlxwxiwuikhpfohgocpbkf...

output:

result:

ok 500000 lines

Test #52:

score: 0

Accepted

time: 1300ms

memory: 270572kb

input:

twcbjagftdkkfjdflnjwusepncuedwpnpknarverzccbwagpubuxkhctxesrjnmdcftmmttvwgjjoruvnhjeljfgxgmnjnkldhrvbebuzjsdcgkvctevuiihuuuwfhdresijnptxfuprmrzpjxcsgclgjmeeptwbomndbitamovzhzrhakmtoutspseebrfeoplzsplttpppbemejpepfjiteiuwrimdjdunhwflkdohzwdgclnrzwwhlowgihnpdxtgostzgnsekdiknwjafeirolwpewwpotdnxhojtaco...

output:

result:

ok 500000 lines

Test #53:

score: 0

Accepted

time: 1293ms

memory: 265680kb

input:

fmcvbauqftqyhkkhyxuenmuznnnuyahgrhytqylbadjbkjrmixgrcktlqldysebefqmwpjfdbeveauxqyxdbuqzwrcliumkcapumacajgdziwnyfrjafzagptvaufedigkyksveucbsewhcjymxeiayiizimbcgpuidmjwujztlyiktrbeiunzwhaanzyacixpcyhkfzvrcgcngtwvtsxexfjgzjxgwczyswhwkbfbljqbyaftsuyfxqvdyvllztpsueblqzpcdxinpkiphikbwaanbdxjnqbtmdruypcyme...

output:

result:

ok 500000 lines

Test #54:

score: 0

Accepted

time: 1262ms

memory: 264648kb

input:

yqywldzsssmtbzkvoqtlefqgubkfkwnyetdnfvqzlslzoaqdbaxotlhvuqaojxddhakjcmjevfztbzubelgkhbxfcuqtutxxrlkcasbqmwzkakputefodutfvszsbxljngfhpofjezqqbqneojbdeiedudhtjxizdfkqfyrqyurtaebzhpcrgcatdluvuzwhzksecebdybmhdywfdpsdfotlzhzwzwlhgsmhyilyltxefshtwgunogehaulranpdygevgxsmoaftxqydvzqmivvotayltggcrzmefqzknrmg...

output:

result:

ok 500000 lines

Test #55:

score: 0

Accepted

time: 710ms

memory: 345976kb

input:

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

result:

ok 500000 lines

Test #56:

score: 0

Accepted

time: 699ms

memory: 343612kb

input:

dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

result:

ok 500000 lines

Test #57:

score: 0

Accepted

time: 772ms

memory: 338204kb

input:

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh...

output:

result:

ok 500000 lines

Test #58:

score: 0

Accepted

time: 912ms

memory: 327312kb

input:

pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

result:

ok 500000 lines

Test #59:

score: 0

Accepted

time: 1126ms

memory: 316016kb

input:

zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

result:

ok 500000 lines