QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#666885#266. 广义后缀自动机xx_mmcAC ✓218ms243132kbC++172.7kb2024-10-22 20:19:242024-10-22 20:19:31

Judging History

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

  • [2024-10-22 20:19:31]
  • 评测
  • 测评结果:AC
  • 用时:218ms
  • 内存:243132kb
  • [2024-10-22 20:19:24]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

struct SAM
{
    static constexpr int SIZE = 26;
    struct Node {
        int len;
        int link;
        int cnt;
        array<int, SIZE> next;
        Node():len{}, link{}, cnt{}, next{} {}
    };
    vector<Node> t;
    SAM() { init();}
    void init() 
    {
        t.assign(2, Node());
        t[0].next.fill(1);
        t[0].len = -1;
    }
    int newNode()
    {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c)
    {
        if (t[p].next[c])
        {
            int q = t[p].next[c];
            if (t[q].len == t[p].len + 1) return q;
            int r = newNode();
            t[r].len = t[p].len + 1;
            t[r].link = t[q].link;
            t[r].next = t[q].next;
            t[q].link = r;
            while (t[p].next[c] == q)
            {
                t[p].next[c] = r;
                p = t[p].link;
            }
            return r;
        }
        int cur = newNode();
        t[cur].len = t[p].len + 1;
        while (!t[p].next[c])
        {
            t[p].next[c] = cur;
            p = t[p].link;
        }
        t[cur].link = extend(p, c);
        t[cur].cnt = 1;
        return cur;
    }
    int extend(int p, char c, char offset = 'a') {
        return extend(p, c - offset);
    }
    int next(int p, int x) {
        return t[p].next[x];
    }
    int next(int p, char c, char offset = 'a') {
        return next(p, c - offset);
    }
    int link(int p) {
        return t[p].link;
    }
    int len(int p) {
        return t[p].len;
    }
    int cnt(int p) {
        return t[p].cnt;
    }
    int size() {
        return t.size();
    }

    long long ans;
    vector<vector<int>> adj;
    void build()
    {
        ans = 0;
        adj.assign(t.size(), vector<int>());
        for (int i = 2; i < t.size(); i++) adj[t[i].link].push_back(i);
        get_cnt(1);
    }
    void get_cnt(int x)
    {
        for (int y : adj[x])
        {
            get_cnt(y);
            t[x].cnt += t[y].cnt;
        }
        if (t[x].cnt > 1) ans = max(ans, 1ll * t[x].cnt * t[x].len);
    }
};



void solve() {
    int n;
    cin >> n;
    SAM sam;
    while (n--) {
        string s;
        cin >> s;
        for (int i = 0, p = 1; i < s.size(); i++) {
            p = sam.extend(p, s[i] - 'a');
        }
    }
    long long ans = 0;
    for (int i = 2; i < sam.t.size(); i++) {
        ans += sam.t[i].len - sam.t[sam.t[i].link].len;
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 126ms
memory: 241024kb

input:

16854
dbfbkkafejhhdnicdljkgbaanjhaehbgbjihdaillhnabangegbfmgaijfee
ebaffeadeddebcefdbfbddaafbbecbacaeefcfdabccdeaabfbadcdcdffdd
lflglkkeehkaglgakbgabhggfgfkdkhhcildbidaflgfffjdcbhbekbkhbddi
edeiihegdchicgdggbiaegbbhffgiehdcbfagfcaceggeehdggchccbb
bjglnggimjnknbaeagcmfollngfjgmikcmcioeeffbchknfnlaiad...

output:

23749949

result:

ok answer is '23749949'

Test #2:

score: 0
Accepted
time: 142ms
memory: 242836kb

input:

7669
cedkkifidiefdbfbcjabkcbdcifhajcficehkfiidfdaeceibiaikjdediecekcbihhbkdbjhcecbghgbkehicgeabfgikiijihihjhhdbkjijchfjedageficfgcaagdghg
oefeabmeuufjpmmibcuvqaqtmfuefrcioaqtqiqrangnfwplkeswnribmvejjvlmgjdfunrclowjwctumeoaiwtpoaiegmvsccklrcdjorhnqhgovoghhsfkrcdoanhq
aeedaeaeaaadddbbbadabdcbadddbbebb...

output:

57799793

result:

ok answer is '57799793'

Test #3:

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

input:

16303
cjhrprqdfcapeaaqdiracoaahsbaibgknntacpqkhtcphsklqdflsledhjr
dcfbdefcgfedeaebceadeeeabcbedfaefdebadabcffacecdeeccdaaggga
badacaadacbbaacbacbdabaddddadbbdbcacdcdcccbcaddcabbdbbacaaaccab
dqhfhdqlfncictdekmvtmqbonhchdbbjqocbdveovanqdbrpcaqekclaso
wqwpytgspzmrzbkhjcptzmijrphunyyehquhcalcbhpdjrjebkb...

output:

24767366

result:

ok answer is '24767366'

Test #4:

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

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

input:

14790
iebjifeiddjebdeffebbdjkjfkagejdbjdbdidcjghbjbifkhghecikeaekcefefghjc
kaeiklmadmdllijbokmmfodfenhhamloponmbolmphciincocpkhhckdfldpmapl
nsapmmhijmlmiiafsgqgnqhcalegbshtbrbfbdoinqeqrtdisjkgepqdejdfagpli
dacbbaadbddcdacbbdabbbcdccbdabdaacbcddabbcccdadddbdbbadbdcbbaacacb
fhecdmdmeijceiiamcjlldjmeek...

output:

27533013

result:

ok answer is '27533013'

Test #6:

score: 0
Accepted
time: 119ms
memory: 241716kb

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: 82ms
memory: 123788kb

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: 136ms
memory: 241400kb

input:

6476
jjfcfbcaabhbhhbacgagjjidjabfjcbbhecgcbdgbbghjhcejjjdhefehcbiiefabjadajfighdjgfaiecijhbfbfacgjcfaedejejffjaegbfjggcegggbihfedehfgbhajhaifdieeiibgdjeggccebfdg
ckbakhcficaciaecbccdeejekbceehiiikdhdabgbbjhhjhdccecibaihdbgkjjbjkbjdkhegfajdjecicbcdfbcbbibibebbggegieikfabfgeedgjcfgfbekicechhedcacgibch...

output:

69112648

result:

ok answer is '69112648'

Test #9:

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

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: 94ms
memory: 123256kb

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: 131ms
memory: 241524kb

input:

628
imlhecgjgjjgdbkgkkcciaefdlbmigciflhclkgfjhechjfdfeaggfmjjambjfkailfiiijffcmahhcagkdgiadmmhijcjeigebfkgmjbacckccejahajjgkcbdhmbjjdfaihiehghbekcifkmelhgdggkkebkfcliafmlmdmagekkldaebieclcfaedlhhjabaekfbbekfcifkkdcjkhkdklfakfklbimilkklgeckcjablailjkefcibklmmedlmbjedehibkglbfiejhkmdmggedaelkiaidlcdig...

output:

765629388

result:

ok answer is '765629388'

Test #12:

score: 0
Accepted
time: 136ms
memory: 241084kb

input:

30
hgffjacdidjhihabhbjdghkbakhdgbackkkbciggaefageeegdejbhcigacbjdjiagfaigdfeibgjkajjkdbkgfeibjfkgcifbgagafjgdikijkehcjfhhdijjehcckhjecjkiehiadbafcehbabchdefbigcgfadcdikckbeafijhhjjbfjgjbibihfghejdhacigibcjhkgjajaidhifbbbidbfehcgdadchcjkfghdjjaffadcbgcjiahkjgkdjifaikdebiffjiiecajbaeachccedaijecdfehjk...

output:

16661663625

result:

ok answer is '16661663625'

Test #13:

score: 0
Accepted
time: 107ms
memory: 242996kb

input:

3
lbmoibeicoablgmjjbejhkkngmjmgkdnfecdnjldmjiooehhjfldjnebakimfahndkjdlenfeccjhlimdiohcgjdjbecfjgjcedmadkmedofdajjkfkmohnbnikdhclhkhnladcihkafkmahekihlbdmkhdfdcfikjnodmajbbbicacbonlaaegnokfnaandblgkjhgglggchbhdfgcldakclinfioeomglejhikkjdcdbdkcddhcoahfnbgnidfochnmcgmbjcngohkheioholkfglcamhcjbfaagaejj...

output:

166660584606

result:

ok answer is '166660584606'

Test #14:

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

input:

93
oifqpcdugracedbugpohduedtegfaprfubtfogerrndkfnrcgjeeuceeouooamdemsblcbrsptoanbgbqqejalskbfqcjtrudhmigbqhauvtjoccvtqjhlchtsmdoqvfjkoqkpqfkeqbipmchtsbscfghiickhikmautpltmekbimpdntljoqbhqnphqncerpahshqibfumukegmqctdkklmdmrutarvkglsdonnqllshjakipafibkanhvfuakvjdnhjdgqgskdmbqfhbgrsijbpfotndktspdjqaggo...

output:

5197291378

result:

ok answer is '5197291378'

Test #15:

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

input:

419
bbdaeabebddadbbeedbacabbbecdbeacdadbaebdcedcbebcbbbebbdbccedcbaccdcdaadeaaaecbaccdcdbecddebedcabbdceeaaebeebcbaadbbcbadccedabdbbeedbeaaddbdeadbbceeacbebacabcbeceedddedbbaddeabdeceeaaaacbccbcabeaeadbaaacaaadbeeabadeecdecbdeacaacdbcadbaebebcdebdeebecbdedaabdacddaabacedcddbdeddbbdcaecbabdeebeaebdbb...

output:

1145009288

result:

ok answer is '1145009288'

Test #16:

score: 0
Accepted
time: 31ms
memory: 123600kb

input:

214
azqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevazqbeguwsevbuncqaroqgazqbeguwsevbuncqaroq...

output:

1151326618

result:

ok answer is '1151326618'

Test #17:

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

input:

7224
ajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzajwgyefdzbbjhvniphuajwgyefdzbbjhvnip
aaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswomqmzlgaaswomqmzlgbmxjwjruuaaswom
apcbdqgyhybfzap...

output:

39236949

result:

ok answer is '39236949'

Test #18:

score: 0
Accepted
time: 50ms
memory: 123208kb

input:

11278
alcrkrftlkbxzpcebwxxalcrkrftlkalcrkrftlkbxzpcebwxxalcrkrftlkbxzpcebwxxalcrkrftlkalcrkr
asfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlqsovkbsnkasfgdlqsovkasfgdlqsovkbsnkasfgdlq
aobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdvtuasaoaobfgcdvtuasaobfgcdvtuasaoaobfgcdv
auubvwtruncjauuauubvwtruncja...

output:

26413999

result:

ok answer is '26413999'

Test #19:

score: 0
Accepted
time: 44ms
memory: 123764kb

input:

33
apqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfapqjmltfbygopeezfapqjmltfbygo...

output:

7426319363

result:

ok answer is '7426319363'

Test #20:

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

input:

28
aechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbxrexqdgusaechgbxrexqdgusaechgaechgbx...

output:

8721480282

result:

ok answer is '8721480282'

Test #21:

score: 0
Accepted
time: 181ms
memory: 242132kb

input:

1545
eacfddfabffdfdbbgbcdbgfbfbeccffdddgdagaaaccaaffcabcdcddabcdcdafacddcbbaeafcbbadaefbbbbfffaafgfbbcbeafdegdedbffaccaaffcabdcafgefbfabbggaccbabgggcaadbgcfeefgaceddaaceabdabeedgcebebcgaaceabdabebfcafdeaaacdcddabcdcgdacggedaacdcbfeabgfbageggacegbbggaccbabgebfegbecaefcgbbdgdafeefgacedddfcddfeggcfdege...

output:

316540941

result:

ok answer is '316540941'

Test #22:

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

input:

2916
gdebacaacfebadgdafeedgeadfaebagefffefbggdabcedfegaggdfagdfafdbbffgcfeaedebbbebegedefgeefcgaeccfebbgbedefgeefcgdddfdaedebcdggcggcddgcaecaeeabagabeebfgbaegcfcbaaaedefgeefcgbedbdbcadbdbbffgcfeabfbbadbaaaggdfagdfafeeecfaaeageebfcafedddddfdaedebadgbgdbgcaeebfcafeddffebfeeafdfadfefbadceefgcbabeaffefe...

output:

163900615

result:

ok answer is '163900615'

Test #23:

score: 0
Accepted
time: 155ms
memory: 242196kb

input:

616
fbcdedbfdgcffbcdeadgdbafecgccbbdgcgagcadaefbbdcbcbbdgcgagcadffgfgdgbefgggeadcfcbecefbdfebbfdgffegedbgeacecbeecgefcfaeaefbaddcbaebcbaddcbaebcdbedeedcfcfbdbcfaaeagceccdbbdcecefbdfebbffgfgdgbefbabbdabadfdegaecfgeccffbcdeadgfdgffegedbfbcdedbfdgdbecgdcdedfdgffegedbgceccdbbdcabeabdffbagceccdbbdcbdddaf...

output:

803953105

result:

ok answer is '803953105'

Test #24:

score: 0
Accepted
time: 32ms
memory: 122304kb

input:

487
aaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouaaaaaaaauouhdnbkzzxpcaa...

output:

452762759

result:

ok answer is '452762759'

Test #25:

score: 0
Accepted
time: 32ms
memory: 123132kb

input:

3
aaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgqejhwqijvmqfrlaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaammgaaaaaaaam...

output:

56482697969

result:

ok answer is '56482697969'

Test #26:

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

input:

958
aaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaaaaaaaaaaaaaaaaencfjaa...

output:

224593548

result:

ok answer is '224593548'

Test #27:

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

input:

12095
aaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkaaaamfkciokmombaaaamfkaaaamfkaaa
aaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligyaaaaaaaaaaaaaaaafligy
aaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaaaaaaafsmaaa
aaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaaaaaaaamuvaa...

output:

15304035

result:

ok answer is '15304035'

Test #28:

score: 0
Accepted
time: 44ms
memory: 123688kb

input:

15357
aaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcuaaaaaaaakcukkjnwaaaaaaaakcu
aaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugiaaaaaaaaugia
aaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaaaaaaaaaaaaaaonnpjaaaa
aaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczacjaaaaaaaaaaaaaaaaczac
aaaaaaaawwfaaaaaaaawwfaaaaaaa...

output:

12407081

result:

ok answer is '12407081'

Test #29:

score: 0
Accepted
time: 155ms
memory: 240976kb

input:

8821
hhhhhhghhhhghhhhhhhhhhhhhfhhhhhhhhhhhhhhhhghhghhhhhhhhhghfhghggghhhhghhghhhhhhhhhhhhhhhhfhhhhghggghghghhhhhghhhhhh
hhhhhhhhghhhhgghhhhhhhhgfhhhhghhhhhhhhghhhhhhhhhhfhghghhhheghhhhhghhhgghhghhhhhhhhhhhhhhhhghhhhhhghhhhhhhhhhehhhh
hghhhgghhhhhhhhhhhhehghhhhhhhfhhhgghhhhhhhghhhhhhhhghfhhhgghhffhgh...

output:

39996161

result:

ok answer is '39996161'

Test #30:

score: 0
Accepted
time: 121ms
memory: 123580kb

input:

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

output:

6002528

result:

ok answer is '6002528'

Test #31:

score: 0
Accepted
time: 167ms
memory: 242468kb

input:

12457
lkljlgkllljljklkllljlljljlllkllllllllllljllkllljllllkjkllllllkillkkllkjlkkllkl
llklklllkllilljjllklkljlkjlllkkllkllkkllllkkjjlklllllllkklllllkljllkljlilkllljklll
llklklllkhljjlljllljlljljlllllklllklkklllkllklllkllllllkljllllllllkkllllllllk
llllllkllljkllkjkllllkllllllklllkllikkkllkkglllllkllll...

output:

27420733

result:

ok answer is '27420733'

Test #32:

score: 0
Accepted
time: 181ms
memory: 241648kb

input:

13968
lkllllkjllllllkllljkjljkkllllkllklllklkllllllikllkllllllkillkklkklhk
llljlilklllkllllilkklllllkkllkjlkkllllllklkklljkklllkklkliljlkjllkllllj
lkkllkllkllklkkkjlllllkkkllklhkkklkjllllklllkljllllkklllljljllklkllllllll
lklllkllijlkjlllljllkkllllllllkklllkkllklllllllljllklllllljllhlllllllk
lljllklh...

output:

23006835

result:

ok answer is '23006835'

Test #33:

score: 0
Accepted
time: 184ms
memory: 241008kb

input:

1424
kllklkkllkklkllllllllllkllllljlkllilljlkkkklkllkllljlllljllljklllljkkliljllllklklllkklllllkllljlllklklklklklllllkjljkllllklllliklljlklllllkllllllllllklklllklllllklllllkjlklljjkllllllllllkllkllllllllklllljkllkljlklkljjlljlkkllkkllllkklllllklkllllllllllkllllllkklllllllllllkklkklllllllklkklkllkllk...

output:

336960929

result:

ok answer is '336960929'

Test #34:

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

input:

389
jllllllkljkjillljlllkkllljlklkkllkkllklkkjlllklkllkllllljlllkkklkklkllllllklklkllilklkllklllkjllkkllllkllklkkljkklllllklkjllllillllljkljlllkllljlkllllllkljklkklllllkljlklllklllkikkllkkjllkllilkllkljlllklkllllkkkllkklllllllllilllljilkllkllllllljlklllllllljjkllljllllkilljlkllllljjlkklkjllkllllllkl...

output:

1270722646

result:

ok answer is '1270722646'

Test #35:

score: 0
Accepted
time: 218ms
memory: 242072kb

input:

1
lljllillllkklllklkllllllllllkllkillllkllllklklklllllljkilllllkkkjlllllkllllkklkklllllelkljkklllljlllllllllljllkllljllllljlkkllkkkjllkllllklllllklklkhlllklllllllklljllllklllkllllkgjlkklllllkklllliljlllkkkllkklklllkkllkkjkllllljlkkllklllkjklkllkllklllljkjjlllllllllkljklklllklllilllklkllklllklkllllll...

output:

499986467945

result:

ok answer is '499986467945'

Test #36:

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

input:

557
lllllllllkllkllkkllllllkhlkkjllllkllklkllllkjllkklljlklljllllllljkllliklllilkkjllkllllljllljlllkjlljjjklllllljkkkklljllljlllljjllljllljlllllllllllllkllklflllllljklllllkllljkllljklkklkjllllllkklllllkikllillkllijlllkkllllljlljljjkllllkllllllllllkllkljlllllillllllllllkillkjljklkllillklllllkljllllll...

output:

883262766

result:

ok answer is '883262766'

Test #37:

score: 0
Accepted
time: 67ms
memory: 123720kb

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: 88ms
memory: 123324kb

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: 96ms
memory: 241388kb

input:

3628
aaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyynevwnjssfgatjkuxyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmyaaaaaaaacmywwwyyneaaaaaa
aakmaakmaakmaakmaa...

output:

103987512

result:

ok answer is '103987512'

Test #40:

score: 0
Accepted
time: 120ms
memory: 242084kb

input:

12813
aaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaaaaaaiddesaaaaaaaaaaaa
aaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoaaaaaaaawsoa
asecbauzasecasecbauzasecbauzasecasecbauzasecasecbauzasecbauzasecasecbauzasecbauz
daahekajbnookaegclmcggkffpmcopnmjclpmlgildkmgclpnkgpgpclen...

output:

26912166

result:

ok answer is '26912166'

Test #41:

score: 0
Accepted
time: 119ms
memory: 242968kb

input:

2
gdcfddceadedgcfgdgcagafbdabdcefcabcafcdggfgfddefdgcfgaebbbbdceggcbddfbgaeggadfbcgafbdabdceeadegegcggedffcccbbecafdgdfdbfgafbdabdcegcbdecdffdccaeecfgecbdaafddccfcaadgagedccfceadabfeegcdeccdaccaadgagedcabafgfcgggedffcccbbecafdgdfdbfdfegccdggcdgfdccgabefbcbacadfafcabcafcdgcfceadabfeceggcbddfbgdcfddce...

output:

249980713640

result:

ok answer is '249980713640'

Test #42:

score: 0
Accepted
time: 111ms
memory: 242656kb

input:

6
llklklllllllllkljkkllljllklikkikjilllljlllkkilllllklllljllklllkjlillljilllkllllilllljlkllllklllljklllklkkkllllklklllllllllllklllllillkkhljkllliiklllllklllkllllljlllllljlkllllkllllelljlkljllllllllllklkjlllkljllllilllklkkkflllkllkllkkllllllllklllilklljlklljlllllkljjjlkllljljlilllllklklkklljkljllilkl...

output:

75007300766

result:

ok answer is '75007300766'

Test #43:

score: 0
Accepted
time: 102ms
memory: 242904kb

input:

11005
illllkkllllllljlllllkljlklkllllklllllklkllllllkklllklkllklllklllllkklllkllljlllhljjllklllll
lllklkljllkillklkljlllklllllllllljlljkllllklklklllllllllklllljkljlllllllklkkjllllllllijllll
lllljllkklkkillllllkllllllklklkkjlllllklllllllljlllllkllklllkllillllkiljlkllklkkjklllkkk
aaaaaaaaqzzaaaaaaaaqz...

output:

31075980

result:

ok answer is '31075980'

Test #44:

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

input:

168
edfdgadafegedbfbeefccfebdfebfdbfgcadbbecedfdgadafedfdeegdgbabebefdccdfbgegcaggacfacccabbggcacdbfcccbdfgbadeffabcbafcedggffdbgagfbdfdcfccagggdafeedfebdcdfcggdgdcgbgfcaefeddcecggbefccacdbfcccbfcfcdccbdcbeafdeefeddfdeegdgbabfgcadbbecaaeacdcdaaefffedgdedfcfgcedabbfffdaeecadbcbafcedggbgbaaccdfdbgegca...

output:

2221581860

result:

ok answer is '2221581860'

Test #45:

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

input:

34
lkllllllllilljkllllllkkjllllllllkiljkklkklklllllkkllllkllkljgllkliklllkllkllllllklllljlklllllklllllllljlijklklllkkklkjlllllklllllljllklllljlkllklllljllejlllllllllklllklllkljklljikjllllllllljllljllkklllllllllllllllkllllkllllllhljlllljlllkllkllkllllklllkillkkljlljlklllkljkllllljklllllljllllkkklllll...

output:

11609354185

result:

ok answer is '11609354185'

Test #46:

score: 0
Accepted
time: 115ms
memory: 242216kb

input:

1093
lllllllllllkjllllklkklllkkljllllkkjlklllllkkllllklllkllllllkllkllllklkllkkjlljlllkklllliklkiljklilljllljlllhlkklklllllkllkljililllkllklllllkllklllllljlllllkllkllllljlllllllklllkklkllllkllllllklllkllllhkkllljllkllllkkllkljlllllllllkkllllllklllkllkllllilkllljlllllljjlljjklkklklkjlljkllllllllkllll...

output:

354111743

result:

ok answer is '354111743'

Test #47:

score: 0
Accepted
time: 123ms
memory: 242032kb

input:

71
jlkllkklllllkkklilkllkllllllllllklllljllllljkklllllllllhllllkkkllkjkllllllhlllillllllkkllllhlklllllllllkkllkkkjlkklkllllllkjlclkjllllklkllkljlkllklkljkllllllllljlhlkllllkilklllkjllljljlkllllkklklllllllklllklkkjllkkklllhjlllllllkklllllkllkllllllkklfkljllklllljllkllllkllkkljllkklljlllllllllikllkkll...

output:

5329897030

result:

ok answer is '5329897030'

Test #48:

score: 0
Accepted
time: 136ms
memory: 241472kb

input:

308
jcicgcibjfhcedjjbefddaafdcfdjeadeefgcfhjjbjgdhcgjigdaaefjdcdgjdaagggbjbbjgjbcaijedaccgieedfahebheabcceijcaecabidjajijedfjaaggcghdjibjjicbhjafcdhigcbgeaedehajbcfhhadefcgibjigfiggiibghcjiabjajggcjgbabfbbdaeadhabheahfbhjbchbehiighabdcgaicfjiechaeddeaeejicifigdeaeicdieabefijcbffbfhhbijgiciihgcdeghac...

output:

1245588935

result:

ok answer is '1245588935'

Test #49:

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

input:

396
aaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkaaaaaaaawlkiwtpadegjxaa...

output:

992295088

result:

ok answer is '992295088'

Test #50:

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

input:

2312
abvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqabvfbqfgqbpllvmiabvfbqfgqbpllvm...

output:

163513482

result:

ok answer is '163513482'