QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#480240#266. 广义后缀自动机lmeowdn#AC ✓226ms262092kbC++142.6kb2024-07-16 11:14:442024-07-16 11:14:44

Judging History

This is the latest submission verdict.

  • [2024-07-16 11:14:44]
  • Judged
  • Verdict: AC
  • Time: 226ms
  • Memory: 262092kb
  • [2024-07-16 11:14:44]
  • Submitted

answer

//Shirasu Azusa 2024.7
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x)  {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x)  {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x)  {return (x==0?-1:__builtin_ctzll(x));}

#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;  
typedef vector<int> vi;
typedef vector<pii> vp;
typedef tuple<int,int,int> tiii;
int read() {
  int x=0,w=1; char c=getchar(); 
  while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
  while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();} 
  return x*w;
}

const int N=2.2e6+5;
char s[N];

namespace SufT {
  signed ch[N][28];
  signed l[N],link[N],st[N],n,s[N],now=1,r,last,tot=1,cc[N];
  int newn(int _s,int _l=N) {
    ++tot; l[tot]=_l, st[tot]=_s, link[tot]=1; return tot;
  }
  void init() {
    l[0]=N, tot=1;
  }
  void extend(int x) {
    s[++n]=x; r++; last=1;
    if(x>=26) cc[n]=n;
    for(;r;now==1?r--:now=link[now]) {
      while(r>l[ch[now][s[n-r+1]]])
        r-=l[now=ch[now][s[n-r+1]]];
      int v=ch[now][s[n-r+1]], c=s[st[v]+r-1];
      if(x==c||!v) {
        link[last]=now, last=now;
        if(!v) ch[now][s[n-r+1]]=newn(n-r+1); else break;
      } else {
        int u=newn(st[v],r-1);
        ch[u][c]=v, ch[u][x]=newn(n);
        st[v]+=r-1, l[v]-=r-1, ch[now][s[n-r+1]]=u;
        link[last]=u, last=u;
      }
    }
  }
  void getcc() {
    per(i,n,1) if(!cc[i]) cc[i]=cc[i+1];
  }
  int dfs(int u) {
    int res=0;
    rep(i,0,25) if(ch[u][i]) {
      int v=ch[u][i];
      int L=st[v], r=st[v]+l[v]-1;
      if(cc[L]<=r) {
        rep(j,0,25) ch[v][j]=0;
        l[v]=cc[L]-st[v];
        assert(l[v]>=0);
      } else {
        res+=dfs(v);
      }
      res+=l[v];
    } return res;
  }
}

signed main() {
  int n=read(); SufT::init();
  while(n--) {
    scanf("%s",s+1); int m=strlen(s+1);
    rep(i,1,m) SufT::extend(s[i]-'a');
    if(n) SufT::extend(26);
  }
  SufT::extend(27); SufT::getcc();
  assert(SufT::r==0);
  printf("%lld\n",SufT::dfs(1));
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 148ms
memory: 187372kb

input:

16854
dbfbkkafejhhdnicdljkgbaanjhaehbgbjihdaillhnabangegbfmgaijfee
ebaffeadeddebcefdbfbddaafbbecbacaeefcfdabccdeaabfbadcdcdffdd
lflglkkeehkaglgakbgabhggfgfkdkhhcildbidaflgfffjdcbhbekbkhbddi
edeiihegdchicgdggbiaegbbhffgiehdcbfagfcaceggeehdggchccbb
bjglnggimjnknbaeagcmfollngfjgmikcmcioeeffbchknfnlaiad...

output:

23749949

result:

ok answer is '23749949'

Test #2:

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

input:

7669
cedkkifidiefdbfbcjabkcbdcifhajcficehkfiidfdaeceibiaikjdediecekcbihhbkdbjhcecbghgbkehicgeabfgikiijihihjhhdbkjijchfjedageficfgcaagdghg
oefeabmeuufjpmmibcuvqaqtmfuefrcioaqtqiqrangnfwplkeswnribmvejjvlmgjdfunrclowjwctumeoaiwtpoaiegmvsccklrcdjorhnqhgovoghhsfkrcdoanhq
aeedaeaeaaadddbbbadabdcbadddbbebb...

output:

57799793

result:

ok answer is '57799793'

Test #3:

score: 0
Accepted
time: 138ms
memory: 190620kb

input:

16303
cjhrprqdfcapeaaqdiracoaahsbaibgknntacpqkhtcphsklqdflsledhjr
dcfbdefcgfedeaebceadeeeabcbedfaefdebadabcffacecdeeccdaaggga
badacaadacbbaacbacbdabaddddadbbdbcacdcdcccbcaddcabbdbbacaaaccab
dqhfhdqlfncictdekmvtmqbonhchdbbjqocbdveovanqdbrpcaqekclaso
wqwpytgspzmrzbkhjcptzmijrphunyyehquhcalcbhpdjrjebkb...

output:

24767366

result:

ok answer is '24767366'

Test #4:

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

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: 139ms
memory: 189332kb

input:

14790
iebjifeiddjebdeffebbdjkjfkagejdbjdbdidcjghbjbifkhghecikeaekcefefghjc
kaeiklmadmdllijbokmmfodfenhhamloponmbolmphciincocpkhhckdfldpmapl
nsapmmhijmlmiiafsgqgnqhcalegbshtbrbfbdoinqeqrtdisjkgepqdejdfagpli
dacbbaadbddcdacbbdabbbcdccbdabdaacbcddabbcccdadddbdbbadbdcbbaacacb
fhecdmdmeijceiiamcjlldjmeek...

output:

27533013

result:

ok answer is '27533013'

Test #6:

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

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: 128ms
memory: 187100kb

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: 143ms
memory: 190432kb

input:

6476
jjfcfbcaabhbhhbacgagjjidjabfjcbbhecgcbdgbbghjhcejjjdhefehcbiiefabjadajfighdjgfaiecijhbfbfacgjcfaedejejffjaegbfjggcegggbihfedehfgbhajhaifdieeiibgdjeggccebfdg
ckbakhcficaciaecbccdeejekbceehiiikdhdabgbbjhhjhdccecibaihdbgkjjbjkbjdkhegfajdjecicbcdfbcbbibibebbggegieikfabfgeedgjcfgfbekicechhedcacgibch...

output:

69112648

result:

ok answer is '69112648'

Test #9:

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

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: 140ms
memory: 191680kb

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: 153ms
memory: 190116kb

input:

628
imlhecgjgjjgdbkgkkcciaefdlbmigciflhclkgfjhechjfdfeaggfmjjambjfkailfiiijffcmahhcagkdgiadmmhijcjeigebfkgmjbacckccejahajjgkcbdhmbjjdfaihiehghbekcifkmelhgdggkkebkfcliafmlmdmagekkldaebieclcfaedlhhjabaekfbbekfcifkkdcjkhkdklfakfklbimilkklgeckcjablailjkefcibklmmedlmbjedehibkglbfiejhkmdmggedaelkiaidlcdig...

output:

765629388

result:

ok answer is '765629388'

Test #12:

score: 0
Accepted
time: 143ms
memory: 190480kb

input:

30
hgffjacdidjhihabhbjdghkbakhdgbackkkbciggaefageeegdejbhcigacbjdjiagfaigdfeibgjkajjkdbkgfeibjfkgcifbgagafjgdikijkehcjfhhdijjehcckhjecjkiehiadbafcehbabchdefbigcgfadcdikckbeafijhhjjbfjgjbibihfghejdhacigibcjhkgjajaidhifbbbidbfehcgdadchcjkfghdjjaffadcbgcjiahkjgkdjifaikdebiffjiiecajbaeachccedaijecdfehjk...

output:

16661663625

result:

ok answer is '16661663625'

Test #13:

score: 0
Accepted
time: 166ms
memory: 203472kb

input:

3
lbmoibeicoablgmjjbejhkkngmjmgkdnfecdnjldmjiooehhjfldjnebakimfahndkjdlenfeccjhlimdiohcgjdjbecfjgjcedmadkmedofdajjkfkmohnbnikdhclhkhnladcihkafkmahekihlbdmkhdfdcfikjnodmajbbbicacbonlaaegnokfnaandblgkjhgglggchbhdfgcldakclinfioeomglejhikkjdcdbdkcddhcoahfnbgnidfochnmcgmbjcngohkheioholkfglcamhcjbfaagaejj...

output:

166660584606

result:

ok answer is '166660584606'

Test #14:

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

input:

93
oifqpcdugracedbugpohduedtegfaprfubtfogerrndkfnrcgjeeuceeouooamdemsblcbrsptoanbgbqqejalskbfqcjtrudhmigbqhauvtjoccvtqjhlchtsmdoqvfjkoqkpqfkeqbipmchtsbscfghiickhikmautpltmekbimpdntljoqbhqnphqncerpahshqibfumukegmqctdkklmdmrutarvkglsdonnqllshjakipafibkanhvfuakvjdnhjdgqgskdmbqfhbgrsijbpfotndktspdjqaggo...

output:

5197291378

result:

ok answer is '5197291378'

Test #15:

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

input:

419
bbdaeabebddadbbeedbacabbbecdbeacdadbaebdcedcbebcbbbebbdbccedcbaccdcdaadeaaaecbaccdcdbecddebedcabbdceeaaebeebcbaadbbcbadccedabdbbeedbeaaddbdeadbbceeacbebacabcbeceedddedbbaddeabdeceeaaaacbccbcabeaeadbaaacaaadbeeabadeecdecbdeacaacdbcadbaebebcdebdeebecbdedaabdacddaabacedcddbdeddbbdcaecbabdeebeaebdbb...

output:

1145009288

result:

ok answer is '1145009288'

Test #16:

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

input:

214
azqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroq...

output:

1151326618

result:

ok answer is '1151326618'

Test #17:

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

input:

7224
ajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvnip
aaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswom
apcbdqgyhybfzap...

output:

39236949

result:

ok answer is '39236949'

Test #18:

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

input:

11278
alcrkrftlkbxzpcebwxxalcrkrftlkalcrkrftlkbxzpcebwxxalcrkrftlkbxzpcebwxxalcrkrftlkalcrkr
asfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlq
aobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdv
auubvwtruncjauuauubvwtruncja...

output:

26413999

result:

ok answer is '26413999'

Test #19:

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

input:

33
apqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygo...

output:

7426319363

result:

ok answer is '7426319363'

Test #20:

score: 0
Accepted
time: 154ms
memory: 261864kb

input:

28
aechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbx...

output:

8721480282

result:

ok answer is '8721480282'

Test #21:

score: 0
Accepted
time: 157ms
memory: 205460kb

input:

1545
eacfddfabffdfdbbgbcdbgfbfbeccffdddgdagaaaccaaffcabcdcddabcdcdafacddcbbaeafcbbadaefbbbbfffaafgfbbcbeafdegdedbffaccaaffcabdcafgefbfabbggaccbabgggcaadbgcfeefgaceddaaceabdabeedgcebebcgaaceabdabebfcafdeaaacdcddabcdcgdacggedaacdcbfeabgfbageggacegbbggaccbabgebfegbecaefcgbbdgdafeefgacedddfcddfeggcfdege...

output:

316540941

result:

ok answer is '316540941'

Test #22:

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

input:

2916
gdebacaacfebadgdafeedgeadfaebagefffefbggdabcedfegaggdfagdfafdbbffgcfeaedebbbebegedefgeefcgaeccfebbgbedefgeefcgdddfdaedebcdggcggcddgcaecaeeabagabeebfgbaegcfcbaaaedefgeefcgbedbdbcadbdbbffgcfeabfbbadbaaaggdfagdfafeeecfaaeageebfcafedddddfdaedebadgbgdbgcaeebfcafeddffebfeeafdfadfefbadceefgcbabeaffefe...

output:

163900615

result:

ok answer is '163900615'

Test #23:

score: 0
Accepted
time: 179ms
memory: 207072kb

input:

616
fbcdedbfdgcffbcdeadgdbafecgccbbdgcgagcadaefbbdcbcbbdgcgagcadffgfgdgbefgggeadcfcbecefbdfebbfdgffegedbgeacecbeecgefcfaeaefbaddcbaebcbaddcbaebcdbedeedcfcfbdbcfaaeagceccdbbdcecefbdfebbffgfgdgbefbabbdabadfdegaecfgeccffbcdeadgfdgffegedbfbcdedbfdgdbecgdcdedfdgffegedbgceccdbbdcabeabdffbagceccdbbdcbdddaf...

output:

803953105

result:

ok answer is '803953105'

Test #24:

score: 0
Accepted
time: 158ms
memory: 258408kb

input:

487
aaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaa...

output:

452762759

result:

ok answer is '452762759'

Test #25:

score: 0
Accepted
time: 148ms
memory: 262092kb

input:

3
aaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgqejhwqijvmqfrlaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaam...

output:

56482697969

result:

ok answer is '56482697969'

Test #26:

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

input:

958
aaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaa...

output:

224593548

result:

ok answer is '224593548'

Test #27:

score: 0
Accepted
time: 143ms
memory: 234784kb

input:

12095
aaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkciokmombaaaamfkaaaamfkaaa
aaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligy
aaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaa
aaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaa...

output:

15304035

result:

ok answer is '15304035'

Test #28:

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

input:

15357
aaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcu
aaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugia
aaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaa
aaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczac
aaaaaaaawwfaaaaaaaawwfaaaaaaa...

output:

12407081

result:

ok answer is '12407081'

Test #29:

score: 0
Accepted
time: 203ms
memory: 230356kb

input:

8821
hhhhhhghhhhghhhhhhhhhhhhhfhhhhhhhhhhhhhhhhghhghhhhhhhhhghfhghggghhhhghhghhhhhhhhhhhhhhhhfhhhhghggghghghhhhhghhhhhh
hhhhhhhhghhhhgghhhhhhhhgfhhhhghhhhhhhhghhhhhhhhhhfhghghhhheghhhhhghhhgghhghhhhhhhhhhhhhhhhghhhhhhghhhhhhhhhhehhhh
hghhhgghhhhhhhhhhhhehghhhhhhhfhhhgghhhhhhhghhhhhhhhghfhhhgghhffhgh...

output:

39996161

result:

ok answer is '39996161'

Test #30:

score: 0
Accepted
time: 182ms
memory: 227252kb

input:

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

output:

6002528

result:

ok answer is '6002528'

Test #31:

score: 0
Accepted
time: 180ms
memory: 224136kb

input:

12457
lkljlgkllljljklkllljlljljlllkllllllllllljllkllljllllkjkllllllkillkkllkjlkkllkl
llklklllkllilljjllklkljlkjlllkkllkllkkllllkkjjlklllllllkklllllkljllkljlilkllljklll
llklklllkhljjlljllljlljljlllllklllklkklllkllklllkllllllkljllllllllkkllllllllk
llllllkllljkllkjkllllkllllllklllkllikkkllkkglllllkllll...

output:

27420733

result:

ok answer is '27420733'

Test #32:

score: 0
Accepted
time: 194ms
memory: 224444kb

input:

13968
lkllllkjllllllkllljkjljkkllllkllklllklkllllllikllkllllllkillkklkklhk
llljlilklllkllllilkklllllkkllkjlkkllllllklkklljkklllkklkliljlkjllkllllj
lkkllkllkllklkkkjlllllkkkllklhkkklkjllllklllkljllllkklllljljllklkllllllll
lklllkllijlkjlllljllkkllllllllkklllkkllklllllllljllklllllljllhlllllllk
lljllklh...

output:

23006835

result:

ok answer is '23006835'

Test #33:

score: 0
Accepted
time: 210ms
memory: 226668kb

input:

1424
kllklkkllkklkllllllllllkllllljlkllilljlkkkklkllkllljlllljllljklllljkkliljllllklklllkklllllkllljlllklklklklklllllkjljkllllklllliklljlklllllkllllllllllklklllklllllklllllkjlklljjkllllllllllkllkllllllllklllljkllkljlklkljjlljlkkllkkllllkklllllklkllllllllllkllllllkklllllllllllkklkklllllllklkklkllkllk...

output:

336960929

result:

ok answer is '336960929'

Test #34:

score: 0
Accepted
time: 226ms
memory: 227812kb

input:

389
jllllllkljkjillljlllkkllljlklkkllkkllklkkjlllklkllkllllljlllkkklkklkllllllklklkllilklkllklllkjllkkllllkllklkkljkklllllklkjllllillllljkljlllkllljlkllllllkljklkklllllkljlklllklllkikkllkkjllkllilkllkljlllklkllllkkkllkklllllllllilllljilkllkllllllljlklllllllljjkllljllllkilljlkllllljjlkklkjllkllllllkl...

output:

1270722646

result:

ok answer is '1270722646'

Test #35:

score: 0
Accepted
time: 208ms
memory: 227132kb

input:

1
lljllillllkklllklkllllllllllkllkillllkllllklklklllllljkilllllkkkjlllllkllllkklkklllllelkljkklllljlllllllllljllkllljllllljlkkllkkkjllkllllklllllklklkhlllklllllllklljllllklllkllllkgjlkklllllkklllliljlllkkkllkklklllkkllkkjkllllljlkkllklllkjklkllkllklllljkjjlllllllllkljklklllklllilllklkllklllklkllllll...

output:

499986467945

result:

ok answer is '499986467945'

Test #36:

score: 0
Accepted
time: 212ms
memory: 228768kb

input:

557
lllllllllkllkllkkllllllkhlkkjllllkllklkllllkjllkklljlklljllllllljkllliklllilkkjllkllllljllljlllkjlljjjklllllljkkkklljllljlllljjllljllljlllllllllllllkllklflllllljklllllkllljkllljklkklkjllllllkklllllkikllillkllijlllkkllllljlljljjkllllkllllllllllkllkljlllllillllllllllkillkjljklkllillklllllkljllllll...

output:

883262766

result:

ok answer is '883262766'

Test #37:

score: 0
Accepted
time: 132ms
memory: 190208kb

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: 115ms
memory: 190088kb

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: 149ms
memory: 225456kb

input:

3628
aaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyynevwnjssfgatjkuxyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaa
aakmaakmaakmaakmaa...

output:

103987512

result:

ok answer is '103987512'

Test #40:

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

input:

12813
aaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaa
aaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoa
asecbauzasecasecbauzasecbauzasecasecbauzasecasecbauzasecbauzasecasecbauzasecbauz
daahekajbnookaegclmcggkffpmcopnmjclpmlgildkmgclpnkgpgpclen...

output:

26912166

result:

ok answer is '26912166'

Test #41:

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

input:

2
gdcfddceadedgcfgdgcagafbdabdcefcabcafcdggfgfddefdgcfgaebbbbdceggcbddfbgaeggadfbcgafbdabdceeadegegcggedffcccbbecafdgdfdbfgafbdabdcegcbdecdffdccaeecfgecbdaafddccfcaadgagedccfceadabfeegcdeccdaccaadgagedcabafgfcgggedffcccbbecafdgdfdbfdfegccdggcdgfdccgabefbcbacadfafcabcafcdgcfceadabfeceggcbddfbgdcfddce...

output:

249980713640

result:

ok answer is '249980713640'

Test #42:

score: 0
Accepted
time: 138ms
memory: 226976kb

input:

6
llklklllllllllkljkkllljllklikkikjilllljlllkkilllllklllljllklllkjlillljilllkllllilllljlkllllklllljklllklkkkllllklklllllllllllklllllillkkhljkllliiklllllklllkllllljlllllljlkllllkllllelljlkljllllllllllklkjlllkljllllilllklkkkflllkllkllkkllllllllklllilklljlklljlllllkljjjlkllljljlilllllklklkklljkljllilkl...

output:

75007300766

result:

ok answer is '75007300766'

Test #43:

score: 0
Accepted
time: 172ms
memory: 218220kb

input:

11005
illllkkllllllljlllllkljlklkllllklllllklkllllllkklllklkllklllklllllkklllkllljlllhljjllklllll
lllklkljllkillklkljlllklllllllllljlljkllllklklklllllllllklllljkljlllllllklkkjllllllllijllll
lllljllkklkkillllllkllllllklklkkjlllllklllllllljlllllkllklllkllillllkiljlkllklkkjklllkkk
aaaaaaaaqzzaaaaaaaaqz...

output:

31075980

result:

ok answer is '31075980'

Test #44:

score: 0
Accepted
time: 158ms
memory: 235236kb

input:

168
edfdgadafegedbfbeefccfebdfebfdbfgcadbbecedfdgadafedfdeegdgbabebefdccdfbgegcaggacfacccabbggcacdbfcccbdfgbadeffabcbafcedggffdbgagfbdfdcfccagggdafeedfebdcdfcggdgdcgbgfcaefeddcecggbefccacdbfcccbfcfcdccbdcbeafdeefeddfdeegdgbabfgcadbbecaaeacdcdaaefffedgdedfcfgcedabbfffdaeecadbcbafcedggbgbaaccdfdbgegca...

output:

2221581860

result:

ok answer is '2221581860'

Test #45:

score: 0
Accepted
time: 146ms
memory: 232560kb

input:

34
lkllllllllilljkllllllkkjllllllllkiljkklkklklllllkkllllkllkljgllkliklllkllkllllllklllljlklllllklllllllljlijklklllkkklkjlllllklllllljllklllljlkllklllljllejlllllllllklllklllkljklljikjllllllllljllljllkklllllllllllllllkllllkllllllhljlllljlllkllkllkllllklllkillkkljlljlklllkljkllllljklllllljllllkkklllll...

output:

11609354185

result:

ok answer is '11609354185'

Test #46:

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

input:

1093
lllllllllllkjllllklkklllkkljllllkkjlklllllkkllllklllkllllllkllkllllklkllkkjlljlllkklllliklkiljklilljllljlllhlkklklllllkllkljililllkllklllllkllklllllljlllllkllkllllljlllllllklllkklkllllkllllllklllkllllhkkllljllkllllkkllkljlllllllllkkllllllklllkllkllllilkllljlllllljjlljjklkklklkjlljkllllllllkllll...

output:

354111743

result:

ok answer is '354111743'

Test #47:

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

input:

71
jlkllkklllllkkklilkllkllllllllllklllljllllljkklllllllllhllllkkkllkjkllllllhlllillllllkkllllhlklllllllllkkllkkkjlkklkllllllkjlclkjllllklkllkljlkllklkljkllllllllljlhlkllllkilklllkjllljljlkllllkklklllllllklllklkkjllkkklllhjlllllllkklllllkllkllllllkklfkljllklllljllkllllkllkkljllkklljlllllllllikllkkll...

output:

5329897030

result:

ok answer is '5329897030'

Test #48:

score: 0
Accepted
time: 138ms
memory: 228872kb

input:

308
jcicgcibjfhcedjjbefddaafdcfdjeadeefgcfhjjbjgdhcgjigdaaefjdcdgjdaagggbjbbjgjbcaijedaccgieedfahebheabcceijcaecabidjajijedfjaaggcghdjibjjicbhjafcdhigcbgeaedehajbcfhhadefcgibjigfiggiibghcjiabjajggcjgbabfbbdaeadhabheahfbhjbchbehiighabdcgaicfjiechaeddeaeejicifigdeaeicdieabefijcbffbfhhbijgiciihgcdeghac...

output:

1245588935

result:

ok answer is '1245588935'

Test #49:

score: 0
Accepted
time: 143ms
memory: 226940kb

input:

396
aaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaa...

output:

992295088

result:

ok answer is '992295088'

Test #50:

score: 0
Accepted
time: 166ms
memory: 226644kb

input:

2312
abvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvm...

output:

163513482

result:

ok answer is '163513482'