QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#125674#266. 广义后缀自动机1234567890#AC ✓127ms192528kbC++142.2kb2023-07-17 10:30:412023-07-17 10:30:43

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-17 10:30:43]
  • 评测
  • 测评结果:AC
  • 用时:127ms
  • 内存:192528kb
  • [2023-07-17 10:30:41]
  • 提交

answer

/*
灏忓簾鐗╋紝杩欓兘涓嶄細 /cf
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
//char buf[1 << 21], *p1 = buf, *p2 = buf;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline void write(ll x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
inline ll quickmod(ll x, ll y) {
	ll Ans = 1;
	while(y) {
		if(y & 1) Ans = (1ll * Ans * x) % mod;
		x = (1ll * x * x) % mod;
		y >>= 1;
	}
	return Ans;
}
inline void Add(ll &x, ll y) {
	x += y;
	if(x >= mod) x -= mod;
}
inline void Dec(ll &x, ll y) {
	x -= y;
	if(x < 0) x += mod;
}
inline ll add(ll x, ll y) {
	x += y;
	if(x >= mod) x -= mod;
	return x;
}
inline ll dec(ll x, ll y) {
	x -= y;
	if(x < 0) x += mod;
	return x;
}
char ch[1000005];
struct SAM {
	ll tot = 1, Lst = 1;
	int t[2000005][26], len[2000005], fa[2000005];
	inline ll insert(ll lst, ll c) {
		ll p = lst, np = lst = ++tot;
		len[np] = len[p] + 1;
		while(p && !t[p][c]) t[p][c] = np, p = fa[p];
		if(!p) fa[np] = 1;
		else {
			ll x = t[p][c];
			if(len[x] == len[p] + 1) fa[np] = x;
			else {
				ll ano = ++tot;
				len[ano] = len[p] + 1, fa[ano] = fa[x];
				memcpy(t[ano], t[x], sizeof (t[x]));
				fa[x] = fa[np] = ano;
				while(p && t[p][c] == x) t[p][c] = ano, p = fa[p];
			} 
		}
		return Lst = lst;
	}
	inline ll get_ans() {
		ll Ans = 0;
		for(ll i = 2; i <= tot; i++) Ans += len[i] - len[fa[i]];
		return Ans;
	}
}S;
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	ll T = read();
	while(T--) {
		S.Lst = 1;
		scanf("%s", ch + 1);
		ll n = (ll)strlen(ch + 1);
		for(ll i = 1; i <= n; i++) S.insert(S.Lst, ch[i] - 'a');
	}
	write(S.get_ans()), putchar('\n');
	return 0;
}
/*
*/

詳細信息

Test #1:

score: 100
Accepted
time: 87ms
memory: 152064kb

input:

16854
dbfbkkafejhhdnicdljkgbaanjhaehbgbjihdaillhnabangegbfmgaijfee
ebaffeadeddebcefdbfbddaafbbecbacaeefcfdabccdeaabfbadcdcdffdd
lflglkkeehkaglgakbgabhggfgfkdkhhcildbidaflgfffjdcbhbekbkhbddi
edeiihegdchicgdggbiaegbbhffgiehdcbfagfcaceggeehdggchccbb
bjglnggimjnknbaeagcmfollngfjgmikcmcioeeffbchknfnlaiad...

output:

23749949

result:

ok answer is '23749949'

Test #2:

score: 0
Accepted
time: 80ms
memory: 156060kb

input:

7669
cedkkifidiefdbfbcjabkcbdcifhajcficehkfiidfdaeceibiaikjdediecekcbihhbkdbjhcecbghgbkehicgeabfgikiijihihjhhdbkjijchfjedageficfgcaagdghg
oefeabmeuufjpmmibcuvqaqtmfuefrcioaqtqiqrangnfwplkeswnribmvejjvlmgjdfunrclowjwctumeoaiwtpoaiegmvsccklrcdjorhnqhgovoghhsfkrcdoanhq
aeedaeaeaaadddbbbadabdcbadddbbebb...

output:

57799793

result:

ok answer is '57799793'

Test #3:

score: 0
Accepted
time: 83ms
memory: 152540kb

input:

16303
cjhrprqdfcapeaaqdiracoaahsbaibgknntacpqkhtcphsklqdflsledhjr
dcfbdefcgfedeaebceadeeeabcbedfaefdebadabcffacecdeeccdaaggga
badacaadacbbaacbacbdabaddddadbbdbcacdcdcccbcaddcabbdbbacaaaccab
dqhfhdqlfncictdekmvtmqbonhchdbbjqocbdveovanqdbrpcaqekclaso
wqwpytgspzmrzbkhjcptzmijrphunyyehquhcalcbhpdjrjebkb...

output:

24767366

result:

ok answer is '24767366'

Test #4:

score: 0
Accepted
time: 84ms
memory: 137596kb

input:

40292
aaaaaaaaaaaaaaaaaaaaaa
ibbgbhbhflafhcegickcblef
aeabeebaecccecaacddeebcccd
iamebukjlqboetcabbeqpeuqa
cuauhsdchmsavllgpmstsymycg
vamnscovqvwmbijklralieh
hogfmeigpgckdbohllaof
cccikicbgfgjiggjcijfmha
idprphjhgvlolscmwjeaim
aaabcaacaccbcaacbcbcaa
oltewmxvojyauhijpwujc
gaimfkafahafkfkgehbkbeajl
xh...

output:

7321836

result:

ok answer is '7321836'

Test #5:

score: 0
Accepted
time: 72ms
memory: 152192kb

input:

14790
iebjifeiddjebdeffebbdjkjfkagejdbjdbdidcjghbjbifkhghecikeaekcefefghjc
kaeiklmadmdllijbokmmfodfenhhamloponmbolmphciincocpkhhckdfldpmapl
nsapmmhijmlmiiafsgqgnqhcalegbshtbrbfbdoinqeqrtdisjkgepqdejdfagpli
dacbbaadbddcdacbbdabbbcdccbdabdaacbcddabbcccdadddbdbbadbdcbbaacacb
fhecdmdmeijceiiamcjlldjmeek...

output:

27533013

result:

ok answer is '27533013'

Test #6:

score: 0
Accepted
time: 90ms
memory: 145176kb

input:

31942
fjdghflekibgggabkbcaedgldjklkbljf
kendafnjkigdeckgogqakmpglhkp
fadhdkihqsjofajkjfmdmpgksjesqclq
hidfjeifhcjejkbkbfamhmglgkfeddcnh
dgbjdebbfjgedeggbfjhgefggiaab
ebbbeaedaeabeadeeabbdcbaaecca
cbdfggdecaggehddfebacaecahffddcdh
eqdnlcqjklgldbaqibmecbklhenj
onelfmgdpjhnnlbfjpdbnaecjfpj
dbceeceaeddf...

output:

10679241

result:

ok answer is '10679241'

Test #7:

score: 0
Accepted
time: 75ms
memory: 141772kb

input:

44576
djmtdsnmedihgdgmonrr
bgcrtdbelgbnaotklht
cimfbcabdejefhaiimggg
cecddeageaafccdddefbf
jdlfcnidklhfdfideee
crtewbcgbqjgbibbqfdld
aihadejflleikellhjd
ebcdebeeaaaebbdacdee
aaaaaaaaaaaaaaaaaaa
babbbaabbbccbbbbcaabaaba
imkggkkkdmaflemeeffbkf
ibnngbupkcnhlrqqhsnmhl
defebbdadaeabccfbeffcd
weiyxmcprsuz...

output:

6536763

result:

ok answer is '6536763'

Test #8:

score: 0
Accepted
time: 90ms
memory: 155192kb

input:

6476
jjfcfbcaabhbhhbacgagjjidjabfjcbbhecgcbdgbbghjhcejjjdhefehcbiiefabjadajfighdjgfaiecijhbfbfacgjcfaedejejffjaegbfjggcegggbihfedehfgbhajhaifdieeiibgdjeggccebfdg
ckbakhcficaciaecbccdeejekbceehiiikdhdabgbbjhhjhdccecibaihdbgkjjbjkbjdkhegfajdjecicbcdfbcbbibibebbggegieikfabfgeedgjcfgfbekicechhedcacgibch...

output:

69112648

result:

ok answer is '69112648'

Test #9:

score: 0
Accepted
time: 82ms
memory: 141956kb

input:

44343
wogvpxrljvltdwzcqdey
abbbbfbbbddebedecfaee
ahaiilkbelijigfadci
aplnqearljlegojejke
kneodlkflijjbijnpjopbmi
behbehbgjdeaifihjehh
adkjifcjjdbkkledeabkfm
sscjodcnkoogqjpbmsoqgmh
lgdpiiqlhhcoaedoajga
idedhdeedbleflhedlh
hikdgfekfjjciijkdkek
bbbbbcbabacbbbaaaababcbc
fbhbfeadbghcbebeccggiegc
nfeqovi...

output:

6505168

result:

ok answer is '6505168'

Test #10:

score: 0
Accepted
time: 84ms
memory: 141436kb

input:

49659
egbcjgakcagkkelfkbfhhc
ibekgejgeikfbfbddd
aaaaaaaaaaaaaaaaaa
irobkkijqchelckoe
ccccbcbbcbcbabcabca
hechfcfdgefgcaeggf
babbbbabbabbbbaabbabb
nmggfudhtkdnotnfecrutg
ljhtbkljbdqbsmakp
ddbccacbbbacdccdaaabad
aaddagbedaafabebfe
qgdgivhkarbegcgcqn
tatkdtptpsnloopcenmp
abcnbgkuajowldgldgn
ngrflrnaflp...

output:

5713177

result:

ok answer is '5713177'

Test #11:

score: 0
Accepted
time: 75ms
memory: 159620kb

input:

628
imlhecgjgjjgdbkgkkcciaefdlbmigciflhclkgfjhechjfdfeaggfmjjambjfkailfiiijffcmahhcagkdgiadmmhijcjeigebfkgmjbacckccejahajjgkcbdhmbjjdfaihiehghbekcifkmelhgdggkkebkfcliafmlmdmagekkldaebieclcfaedlhhjabaekfbbekfcifkkdcjkhkdklfakfklbimilkklgeckcjablailjkefcibklmmedlmbjedehibkglbfiejhkmdmggedaelkiaidlcdig...

output:

765629388

result:

ok answer is '765629388'

Test #12:

score: 0
Accepted
time: 90ms
memory: 157292kb

input:

30
hgffjacdidjhihabhbjdghkbakhdgbackkkbciggaefageeegdejbhcigacbjdjiagfaigdfeibgjkajjkdbkgfeibjfkgcifbgagafjgdikijkehcjfhhdijjehcckhjecjkiehiadbafcehbabchdefbigcgfadcdikckbeafijhhjjbfjgjbibihfghejdhacigibcjhkgjajaidhifbbbidbfehcgdadchcjkfghdjjaffadcbgcjiahkjgkdjifaikdebiffjiiecajbaeachccedaijecdfehjk...

output:

16661663625

result:

ok answer is '16661663625'

Test #13:

score: 0
Accepted
time: 46ms
memory: 169280kb

input:

3
lbmoibeicoablgmjjbejhkkngmjmgkdnfecdnjldmjiooehhjfldjnebakimfahndkjdlenfeccjhlimdiohcgjdjbecfjgjcedmadkmedofdajjkfkmohnbnikdhclhkhnladcihkafkmahekihlbdmkhdfdcfikjnodmajbbbicacbonlaaegnokfnaandblgkjhgglggchbhdfgcldakclinfioeomglejhikkjdcdbdkcddhcoahfnbgnidfochnmcgmbjcngohkheioholkfglcamhcjbfaagaejj...

output:

166660584606

result:

ok answer is '166660584606'

Test #14:

score: 0
Accepted
time: 84ms
memory: 161128kb

input:

93
oifqpcdugracedbugpohduedtegfaprfubtfogerrndkfnrcgjeeuceeouooamdemsblcbrsptoanbgbqqejalskbfqcjtrudhmigbqhauvtjoccvtqjhlchtsmdoqvfjkoqkpqfkeqbipmchtsbscfghiickhikmautpltmekbimpdntljoqbhqnphqncerpahshqibfumukegmqctdkklmdmrutarvkglsdonnqllshjakipafibkanhvfuakvjdnhjdgqgskdmbqfhbgrsijbpfotndktspdjqaggo...

output:

5197291378

result:

ok answer is '5197291378'

Test #15:

score: 0
Accepted
time: 76ms
memory: 159500kb

input:

419
bbdaeabebddadbbeedbacabbbecdbeacdadbaebdcedcbebcbbbebbdbccedcbaccdcdaadeaaaecbaccdcdbecddebedcabbdceeaaebeebcbaadbbcbadccedabdbbeedbeaaddbdeadbbceeacbebacabcbeceedddedbbaddeabdeceeaaaacbccbcabeaeadbaaacaaadbeeabadeecdecbdeacaacdbcadbaebebcdebdeebecbdedaabdacddaabacedcddbdeddbbdcaecbabdeebeaebdbb...

output:

1145009288

result:

ok answer is '1145009288'

Test #16:

score: 0
Accepted
time: 27ms
memory: 119732kb

input:

214
azqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroq...

output:

1151326618

result:

ok answer is '1151326618'

Test #17:

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

input:

7224
ajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvnip
aaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswom
apcbdqgyhybfzap...

output:

39236949

result:

ok answer is '39236949'

Test #18:

score: 0
Accepted
time: 26ms
memory: 124120kb

input:

11278
alcrkrftlkbxzpcebwxxalcrkrftlkalcrkrftlkbxzpcebwxxalcrkrftlkbxzpcebwxxalcrkrftlkalcrkr
asfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlq
aobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdv
auubvwtruncjauuauubvwtruncja...

output:

26413999

result:

ok answer is '26413999'

Test #19:

score: 0
Accepted
time: 28ms
memory: 117036kb

input:

33
apqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygo...

output:

7426319363

result:

ok answer is '7426319363'

Test #20:

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

input:

28
aechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbx...

output:

8721480282

result:

ok answer is '8721480282'

Test #21:

score: 0
Accepted
time: 96ms
memory: 172664kb

input:

1545
eacfddfabffdfdbbgbcdbgfbfbeccffdddgdagaaaccaaffcabcdcddabcdcdafacddcbbaeafcbbadaefbbbbfffaafgfbbcbeafdegdedbffaccaaffcabdcafgefbfabbggaccbabgggcaadbgcfeefgaceddaaceabdabeedgcebebcgaaceabdabebfcafdeaaacdcddabcdcgdacggedaacdcbfeabgfbageggacegbbggaccbabgebfegbecaefcgbbdgdafeefgacedddfcddfeggcfdege...

output:

316540941

result:

ok answer is '316540941'

Test #22:

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

input:

2916
gdebacaacfebadgdafeedgeadfaebagefffefbggdabcedfegaggdfagdfafdbbffgcfeaedebbbebegedefgeefcgaeccfebbgbedefgeefcgdddfdaedebcdggcggcddgcaecaeeabagabeebfgbaegcfcbaaaedefgeefcgbedbdbcadbdbbffgcfeabfbbadbaaaggdfagdfafeeecfaaeageebfcafedddddfdaedebadgbgdbgcaeebfcafeddffebfeeafdfadfefbadceefgcbabeaffefe...

output:

163900615

result:

ok answer is '163900615'

Test #23:

score: 0
Accepted
time: 57ms
memory: 174632kb

input:

616
fbcdedbfdgcffbcdeadgdbafecgccbbdgcgagcadaefbbdcbcbbdgcgagcadffgfgdgbefgggeadcfcbecefbdfebbfdgffegedbgeacecbeecgefcfaeaefbaddcbaebcbaddcbaebcdbedeedcfcfbdbcfaaeagceccdbbdcecefbdfebbffgfgdgbefbabbdabadfdegaecfgeccffbcdeadgfdgffegedbfbcdedbfdgdbecgdcdedfdgffegedbgceccdbbdcabeabdffbagceccdbbdcbdddaf...

output:

803953105

result:

ok answer is '803953105'

Test #24:

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

input:

487
aaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaa...

output:

452762759

result:

ok answer is '452762759'

Test #25:

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

input:

3
aaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgqejhwqijvmqfrlaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaam...

output:

56482697969

result:

ok answer is '56482697969'

Test #26:

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

input:

958
aaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaa...

output:

224593548

result:

ok answer is '224593548'

Test #27:

score: 0
Accepted
time: 39ms
memory: 120664kb

input:

12095
aaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkciokmombaaaamfkaaaamfkaaa
aaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligy
aaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaa
aaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaa...

output:

15304035

result:

ok answer is '15304035'

Test #28:

score: 0
Accepted
time: 36ms
memory: 125208kb

input:

15357
aaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcu
aaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugia
aaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaa
aaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczac
aaaaaaaawwfaaaaaaaawwfaaaaaaa...

output:

12407081

result:

ok answer is '12407081'

Test #29:

score: 0
Accepted
time: 99ms
memory: 184244kb

input:

8821
hhhhhhghhhhghhhhhhhhhhhhhfhhhhhhhhhhhhhhhhghhghhhhhhhhhghfhghggghhhhghhghhhhhhhhhhhhhhhhfhhhhghggghghghhhhhghhhhhh
hhhhhhhhghhhhgghhhhhhhhgfhhhhghhhhhhhhghhhhhhhhhhfhghghhhheghhhhhghhhgghhghhhhhhhhhhhhhhhhghhhhhhghhhhhhhhhhehhhh
hghhhgghhhhhhhhhhhhehghhhhhhhfhhhgghhhhhhhghhhhhhhhghfhhhgghhffhgh...

output:

39996161

result:

ok answer is '39996161'

Test #30:

score: 0
Accepted
time: 85ms
memory: 156864kb

input:

26075
hhghhhgfghhghhghgghgghhhhhhhhhhhhdhghh
hhghhghhhhhghhhghhhhhhfhhhhhghhhghhhghhh
hhhghhhhhhhhhhghhhghhhhghghggfghhhg
hhhfhghghfhhhhhhhhhhghhhggghhgggghhhhh
hhggfhgfhhfhghhghhghhhhgghghgfhhgghhh
hhhhghhhhhgfhhghhhehgghehhhhhghhghhhd
hhhhghhhhhghhhhhhghhghhhhhhghehhhhhhh
ghhhghhhhghhhhhhhhhhgghgh...

output:

6002528

result:

ok answer is '6002528'

Test #31:

score: 0
Accepted
time: 89ms
memory: 176628kb

input:

12457
lkljlgkllljljklkllljlljljlllkllllllllllljllkllljllllkjkllllllkillkkllkjlkkllkl
llklklllkllilljjllklkljlkjlllkkllkllkkllllkkjjlklllllllkklllllkljllkljlilkllljklll
llklklllkhljjlljllljlljljlllllklllklkklllkllklllkllllllkljllllllllkkllllllllk
llllllkllljkllkjkllllkllllllklllkllikkkllkkglllllkllll...

output:

27420733

result:

ok answer is '27420733'

Test #32:

score: 0
Accepted
time: 104ms
memory: 174188kb

input:

13968
lkllllkjllllllkllljkjljkkllllkllklllklkllllllikllkllllllkillkklkklhk
llljlilklllkllllilkklllllkkllkjlkkllllllklkklljkklllkklkliljlkjllkllllj
lkkllkllkllklkkkjlllllkkkllklhkkklkjllllklllkljllllkklllljljllklkllllllll
lklllkllijlkjlllljllkkllllllllkklllkkllklllllllljllklllllljllhlllllllk
lljllklh...

output:

23006835

result:

ok answer is '23006835'

Test #33:

score: 0
Accepted
time: 127ms
memory: 191296kb

input:

1424
kllklkkllkklkllllllllllkllllljlkllilljlkkkklkllkllljlllljllljklllljkkliljllllklklllkklllllkllljlllklklklklklllllkjljkllllklllliklljlklllllkllllllllllklklllklllllklllllkjlklljjkllllllllllkllkllllllllklllljkllkljlklkljjlljlkkllkkllllkklllllklkllllllllllkllllllkklllllllllllkklkklllllllklkklkllkllk...

output:

336960929

result:

ok answer is '336960929'

Test #34:

score: 0
Accepted
time: 105ms
memory: 189672kb

input:

389
jllllllkljkjillljlllkkllljlklkkllkkllklkkjlllklkllkllllljlllkkklkklkllllllklklkllilklkllklllkjllkkllllkllklkkljkklllllklkjllllillllljkljlllkllljlkllllllkljklkklllllkljlklllklllkikkllkkjllkllilkllkljlllklkllllkkkllkklllllllllilllljilkllkllllllljlklllllllljjkllljllllkilljlkllllljjlkklkjllkllllllkl...

output:

1270722646

result:

ok answer is '1270722646'

Test #35:

score: 0
Accepted
time: 114ms
memory: 192528kb

input:

1
lljllillllkklllklkllllllllllkllkillllkllllklklklllllljkilllllkkkjlllllkllllkklkklllllelkljkklllljlllllllllljllkllljllllljlkkllkkkjllkllllklllllklklkhlllklllllllklljllllklllkllllkgjlkklllllkklllliljlllkkkllkklklllkkllkkjkllllljlkkllklllkjklkllkllklllljkjjlllllllllkljklklllklllilllklkllklllklkllllll...

output:

499986467945

result:

ok answer is '499986467945'

Test #36:

score: 0
Accepted
time: 104ms
memory: 191188kb

input:

557
lllllllllkllkllkkllllllkhlkkjllllkllklkllllkjllkklljlklljllllllljkllliklllilkkjllkllllljllljlllkjlljjjklllllljkkkklljllljlllljjllljllljlllllllllllllkllklflllllljklllllkllljkllljklkklkjllllllkklllllkikllillkllijlllkkllllljlljljjkllllkllllllllllkllkljlllllillllllllllkillkjljklkllillklllllkljllllll...

output:

883262766

result:

ok answer is '883262766'

Test #37:

score: 0
Accepted
time: 64ms
memory: 120936kb

input:

72044
aaaaaaaaaaaaaaa
aaaaaaaanloa
lklkllkljkllll
inhorbdfrf
lklillljkkklli
afccbddgbabgbg
klllljlllll
dfegbcgdebcecgb
fngnnclqobnl
totgkbmwwwjdu
aaaaaaaazcq
aaaaaaaaaaaa
biajdbchegbhkkn
ddacegbabg
axkplrbipxxkhw
ahdkgbbhab
aaaaaaaadeoaaa
aaaaaaaamfs
cfaecddccbabed
lllkkllkkl
dgabccdegd
klllklllkll
...

output:

2061320

result:

ok answer is '2061320'

Test #38:

score: 0
Accepted
time: 68ms
memory: 119908kb

input:

79950
arldbnfksvarld
aiiwkbjtd
kjinknnini
aaaaaaaasnda
llllklllklll
aaaaaaaamnk
jllklillklllll
atbbdpbvaqaa
akibndtnlfeaki
ljllllkllklll
aabbdgdgcgcgff
kllllllllkll
dgbfaebedeb
ilklikklkklk
bccdaaaee
aaaaaaaabaqaa
agfbcagfgfcegb
ggcdgadceacdg
aydbpocrgtay
dddbcfedc
gbgffdfeffa
aaaaaaaawn
lllllllilll...

output:

1805568

result:

ok answer is '1805568'

Test #39:

score: 0
Accepted
time: 66ms
memory: 150380kb

input:

3628
aaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyynevwnjssfgatjkuxyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaa
aakmaakmaakmaakmaa...

output:

103987512

result:

ok answer is '103987512'

Test #40:

score: 0
Accepted
time: 55ms
memory: 149700kb

input:

12813
aaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaa
aaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoa
asecbauzasecasecbauzasecbauzasecasecbauzasecasecbauzasecbauzasecasecbauzasecbauz
daahekajbnookaegclmcggkffpmcopnmjclpmlgildkmgclpnkgpgpclen...

output:

26912166

result:

ok answer is '26912166'

Test #41:

score: 0
Accepted
time: 47ms
memory: 180008kb

input:

2
gdcfddceadedgcfgdgcagafbdabdcefcabcafcdggfgfddefdgcfgaebbbbdceggcbddfbgaeggadfbcgafbdabdceeadegegcggedffcccbbecafdgdfdbfgafbdabdcegcbdecdffdccaeecfgecbdaafddccfcaadgagedccfceadabfeegcdeccdaccaadgagedcabafgfcgggedffcccbbecafdgdfdbfdfegccdggcdgfdccgabefbcbacadfafcabcafcdgcfceadabfeceggcbddfbgdcfddce...

output:

249980713640

result:

ok answer is '249980713640'

Test #42:

score: 0
Accepted
time: 40ms
memory: 172376kb

input:

6
llklklllllllllkljkkllljllklikkikjilllljlllkkilllllklllljllklllkjlillljilllkllllilllljlkllllklllljklllklkkkllllklklllllllllllklllllillkkhljkllliiklllllklllkllllljlllllljlkllllkllllelljlkljllllllllllklkjlllkljllllilllklkkkflllkllkllkkllllllllklllilklljlklljlllllkljjjlkllljljlilllllklklkklljkljllilkl...

output:

75007300766

result:

ok answer is '75007300766'

Test #43:

score: 0
Accepted
time: 58ms
memory: 145756kb

input:

11005
illllkkllllllljlllllkljlklkllllklllllklkllllllkklllklkllklllklllllkklllkllljlllhljjllklllll
lllklkljllkillklkljlllklllllllllljlljkllllklklklllllllllklllljkljlllllllklkkjllllllllijllll
lllljllkklkkillllllkllllllklklkkjlllllklllllllljlllllkllklllkllillllkiljlkllklkkjklllkkk
aaaaaaaaqzzaaaaaaaaqz...

output:

31075980

result:

ok answer is '31075980'

Test #44:

score: 0
Accepted
time: 24ms
memory: 150228kb

input:

168
edfdgadafegedbfbeefccfebdfebfdbfgcadbbecedfdgadafedfdeegdgbabebefdccdfbgegcaggacfacccabbggcacdbfcccbdfgbadeffabcbafcedggffdbgagfbdfdcfccagggdafeedfebdcdfcggdgdcgbgfcaefeddcecggbefccacdbfcccbfcfcdccbdcbeafdeefeddfdeegdgbabfgcadbbecaaeacdcdaaefffedgdedfcfgcedabbfffdaeecadbcbafcedggbgbaaccdfdbgegca...

output:

2221581860

result:

ok answer is '2221581860'

Test #45:

score: 0
Accepted
time: 51ms
memory: 155224kb

input:

34
lkllllllllilljkllllllkkjllllllllkiljkklkklklllllkkllllkllkljgllkliklllkllkllllllklllljlklllllklllllllljlijklklllkkklkjlllllklllllljllklllljlkllklllljllejlllllllllklllklllkljklljikjllllllllljllljllkklllllllllllllllkllllkllllllhljlllljlllkllkllkllllklllkillkkljlljlklllkljkllllljklllllljllllkkklllll...

output:

11609354185

result:

ok answer is '11609354185'

Test #46:

score: 0
Accepted
time: 53ms
memory: 152880kb

input:

1093
lllllllllllkjllllklkklllkkljllllkkjlklllllkkllllklllkllllllkllkllllklkllkkjlljlllkklllliklkiljklilljllljlllhlkklklllllkllkljililllkllklllllkllklllllljlllllkllkllllljlllllllklllkklkllllkllllllklllkllllhkkllljllkllllkkllkljlllllllllkkllllllklllkllkllllilkllljlllllljjlljjklkklklkjlljkllllllllkllll...

output:

354111743

result:

ok answer is '354111743'

Test #47:

score: 0
Accepted
time: 55ms
memory: 152780kb

input:

71
jlkllkklllllkkklilkllkllllllllllklllljllllljkklllllllllhllllkkkllkjkllllllhlllillllllkkllllhlklllllllllkkllkkkjlkklkllllllkjlclkjllllklkllkljlkllklkljkllllllllljlhlkllllkilklllkjllljljlkllllkklklllllllklllklkkjllkkklllhjlllllllkklllllkllkllllllkklfkljllklllljllkllllkllkkljllkklljlllllllllikllkkll...

output:

5329897030

result:

ok answer is '5329897030'

Test #48:

score: 0
Accepted
time: 55ms
memory: 151204kb

input:

308
jcicgcibjfhcedjjbefddaafdcfdjeadeefgcfhjjbjgdhcgjigdaaefjdcdgjdaagggbjbbjgjbcaijedaccgieedfahebheabcceijcaecabidjajijedfjaaggcghdjibjjicbhjafcdhigcbgeaedehajbcfhhadefcgibjigfiggiibghcjiabjajggcjgbabfbbdaeadhabheahfbhjbchbehiighabdcgaicfjiechaeddeaeejicifigdeaeicdieabefijcbffbfhhbijgiciihgcdeghac...

output:

1245588935

result:

ok answer is '1245588935'

Test #49:

score: 0
Accepted
time: 42ms
memory: 151112kb

input:

396
aaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaa...

output:

992295088

result:

ok answer is '992295088'

Test #50:

score: 0
Accepted
time: 62ms
memory: 152044kb

input:

2312
abvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvm...

output:

163513482

result:

ok answer is '163513482'