QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#259324#7748. Karshilov's Matching Problem IIucup-team902AC ✓869ms59756kbC++204.0kb2023-11-20 20:21:392023-11-20 20:21:40

Judging History

你现在查看的是测评时间为 2023-11-20 20:21:40 的历史记录

  • [2024-08-25 20:42:55]
  • 自动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:969ms
  • 内存:60336kb
  • [2024-08-25 20:42:18]
  • hack成功,自动添加数据
  • (/hack/789)
  • [2023-11-20 20:21:40]
  • 评测
  • 测评结果:100
  • 用时:869ms
  • 内存:59756kb
  • [2023-11-20 20:21:39]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

#define gc c=getchar()
#define r(x) read(x)
#define ll long long

template<typename T>
inline void read(T &x){
    x=0;T k=1;char gc;
    while(!isdigit(c)){if(c=='-')k=-1;gc;}
    while(isdigit(c)){x=x*10+c-'0';gc;}x*=k;
}

const int N = 1.5e5 + 7;
const int p = 1e9 + 7;
const int base = 137;
const int SIZE = 400;

int be[N];
int L[N];
int R[N];

struct Query{
    int l, r, id;
    inline bool operator < (const Query &a) const{
        return be[l] == be[a.l] ? r < a.r: l < a.l;
    }
}Q[N];


inline int sub(int a, int b){
    return a - b < 0 ? a - b + p : a - b;
}

ll f[N];
ll g[N];
int lenl[N];
int lenr[N];
ll Ans[N];
ll ans;

int Lg[N];
int dep[N];
vector<int> son[N];
int ac[N][20];

void dfs(int x){
    for(int i = 1; ac[x][i] = ac[ac[x][i - 1]][i - 1]; ++i);
    for(auto &v: son[x]){
        ac[v][0] = x;
        dep[v] = dep[x] + 1;
        dfs(v);
    }
}

inline int find(int u, int v){
    if(u <= v) return u;
    for(int i = Lg[dep[u]]; ~i; --i){
        if(ac[u][i] > v){
            u = ac[u][i];
        }
    }
    return ac[u][0];
}

inline ll solve(int l, int r){
    ll ret = 0;
    for(int i = l; i<=r; ++i){
        ret += f[min(r - i + 1, lenr[i])];
    }
    return ret;
}

inline void addr(int l, int r){
    ans += g[find(lenl[r], r - l + 1)];
}

inline void addl(int l, int r){
    ans += f[min(r - l + 1, lenr[l])];
}

inline void Get(int x, int &i){
    int l = R[x] + 1, r = R[x];
    for(ans = 0; be[Q[i].l] == x; ++i){
        if(be[Q[i].r] == x){
            Ans[Q[i].id] = solve(Q[i].l, Q[i].r);
            continue;
        }
        while(r < Q[i].r) addr(l, ++r);
        ll t = ans;
        while(l > Q[i].l) addl(--l, r);
        Ans[Q[i].id] = ans;
        l = R[x] + 1;
        ans = t;
    }
}

char s[N];
char t[N];
int w[N];
int Next[N];

int hashs[N];
int hasht[N];
int pw[N];

vector<int> ins[N];
vector<int> rem[N];

int main(){
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    int n, m; r(n), r(m);
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    for(int i = 1; i <= n; ++i){
        r(w[i]);
        f[i] = f[i - 1] + w[i];
    }
    g[1] = w[1];
    son[0].push_back(1);
    for(int i = 2, j = 0; i <= n; ++i){
        while(s[j + 1] != s[i] && j) j = Next[j];
        if(s[j + 1] == s[i]) ++j;
        Next[i] = j;
        g[i] = w[i] + g[Next[i]];
        son[Next[i]].push_back(i);
    }
    dfs(0);
    pw[0] = 1;
    Lg[0] = -1;
    for(int i = 1; i <= n; ++i){
        hashs[i] = ((ll)hashs[i - 1] * base + s[i]) % p;
        hasht[i] = ((ll)hasht[i - 1] * base + t[i]) % p;
        pw[i] = (ll)pw[i - 1] * base % p;
        Lg[i] = Lg[i >> 1] + 1;
    }
    for(int i = 1; i <= n; ++i){
        int l = i, r = n, ans = i - 1;
        while(l <= r){
            int mid = (l + r) >> 1;
            if(hashs[mid - i + 1] == sub(hasht[mid], (ll)hasht[i - 1] * pw[mid - i + 1] % p)){
                l = mid + 1;
                ans = mid;
            }
            else{
                r = mid - 1;
            }
        }
        lenr[i] = ans - i + 1;
        if(lenr[i]){
            ins[i].push_back(i);
            rem[i + lenr[i]].push_back(i);
        }
    }
    multiset<int> S;
    for(int i = 1; i <= n; ++i){
        for(auto &x: ins[i]){
            S.insert(x);
        }
        for(auto &x: rem[i]){
            S.erase(S.find(x));
        }
        if(S.empty()){
            lenl[i] = 0;
        }
        else{
            lenl[i] = i - *S.begin() + 1;
        }
    }
    for(int i = 1; i <= n; ++i){
        be[i] = (i - 1) / SIZE + 1;
        if(!L[be[i]]) L[be[i]] = i;
        R[be[i]] = i;
    }
    for(int i = 1; i <= m; ++i){
        Q[i].id = i;
        r(Q[i].l), r(Q[i].r);
    }
    sort(Q + 1, Q + m + 1);
    for(int i = 1, x = 1; i <= m; ++x){
        Get(x, i);
    }
    for(int i = 1; i <= m; ++i){
        printf("%lld\n", Ans[i]);
    }
    return 0;
}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

8 5
abbabaab
aababbab
1 2 4 8 16 32 64 128
1 1
2 3
3 5
4 7
1 8

output:

1
3
3
16
38

result:

ok 5 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 28368kb

input:

15 4
heheheheehhejie
heheheheheheheh
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
2 3
4 8
2 6
1 15

output:

3
13
13
174

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 95ms
memory: 44744kb

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

108147037823514
221878585246974
455339807727642
440286198422821
148115747906237
88695249853257
351159618462315
58850354020997
65824434822005
270158033672354
197732558443069
298193894693053
239511187032650
28139154231325
408380171835227
268053430937402
32417121185965
104813548228675
44074926058619
78...

result:

ok 150000 lines

Test #4:

score: 0
Accepted
time: 109ms
memory: 45768kb

input:

150000 150000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

528900815691571
112638556022185
514229554849356
2216206133639915
295388515578381
1658587138269057
652142121207636
166322478628783
490195029871161
1191292846892788
1468501126902703
487990867773908
55994169916421
568966315599642
2522992078581539
2339888502167342
2881203249819745
154700081279584
152537...

result:

ok 150000 lines

Test #5:

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

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

386150762496368
2769669390423140
1025785181073675
1707930121656247
332135612349048
113937878332307
1128519694119799
476402941643931
980441978140407
1004994648999517
676169371268202
2607965889355671
273766796671958
711480908011402
71754482763611
400453994282744
975387094872830
810536618300388
2229061...

result:

ok 150000 lines

Test #6:

score: 0
Accepted
time: 149ms
memory: 45992kb

input:

150000 150000
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

25254725752128652
23497896664383313
15195391464047263
41143572895791434
7513384536045842
8871310939247699
17423823866879881
14601201534396958
6203483865940624
24953281161800570
24776576029495768
1687640411226
31563282955464371
29947970968962218
1149303801639767
5806503923049299
11201332188941891
116...

result:

ok 150000 lines

Test #7:

score: 0
Accepted
time: 271ms
memory: 47532kb

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

4570597927951323
11761063519994765
289982253793476
15684854914181269
19579321543184889
459972639580770
15246459216963247
1833393949769247
22425556248999709
11209560100586843
2883954996867615
14371655418173335
29207399108721
5943079608253242
1664456073054861
27405606916506455
23082758946788297
381175...

result:

ok 150000 lines

Test #8:

score: 0
Accepted
time: 869ms
memory: 59756kb

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5697498028074951
21822720964918437
11237472002329727
84315407720465773
32198634509153899
40728716039967676
5913555967331675
10487781019914529
270012821917938205
239347797488036653
216168445985667902
67452321725546144
457298584810665039
187789940805492303
46241700003064393
242312618101113
42260337439...

result:

ok 150000 lines

Test #9:

score: 0
Accepted
time: 103ms
memory: 43204kb

input:

150000 150000
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:

20591954951726
12208904434175
7662625006262
27638144315127
14991794671504
12693360208820
11037771157715
4373484191175
19325903476164
26048068499431
5723213500221
37836285761904
44407448222078
17672607641771
18226179013226
25664535060427
6571081196245
7364255499121
31338586400498
6963750199271
362906...

result:

ok 150000 lines

Test #10:

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

input:

150000 150000
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:

26679397939583
14744203186201
5444732298002
2682795720153
8097594477750
11849141088914
4460923379501
213037786838
16105345264171
9432794502217
7341906921155
175129395650
26090540252644
7939835388186
1974417753321
13404114384225
3350016113286
11461223687633
11253459438574
10536087601821
410458842950
...

result:

ok 150000 lines

Test #11:

score: 0
Accepted
time: 34ms
memory: 25536kb

input:

1000 150000
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababba...

output:

14533294687
36404448099
4898807521
8311487449
101191999742
73649429237
64160767440
94533233142
11330483415
11891445585
32475987658
20881014384
19725249244
46562700910
8954411927
15493987162
95870286230
21115698529
2452671987
14439012748
11977731306
12229300727
74351907054
22843320780
40597085949
512...

result:

ok 150000 lines

Test #12:

score: 0
Accepted
time: 34ms
memory: 25292kb

input:

1000 150000
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababba...

output:

54399359946
51977853051
49357792746
110019851897
69572597913
15709337251
55079579625
23693208641
171669911
1351037076
76795212797
40916790174
98891460109
3646721871
18505243674
61205775419
75138278275
44089408535
5074434752
50936710571
136345768092
19271144823
46362641831
62317616153
37671155153
162...

result:

ok 150000 lines

Test #13:

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

input:

150000 150000
abbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbaabbabaabbaababbabaababbaabbabaababbabaabbaababbabaababbaabbabaabbaababbaabbabaababbabaabbaababbabaababbaabbabaababbabaabbaabab...

output:

38772069365927
38538545381556
38743522830612
38518262255568
38627306791107
38755103769862
38514395190995
38435548368667
38617960233472
38622898369466
38889725443048
38186753347601
38497568337263
38450570197606
38842403793276
38762153954801
38493442696613
38782127536129
38449780600849
38538849423248
...

result:

ok 150000 lines

Test #14:

score: 0
Accepted
time: 37ms
memory: 25180kb

input:

1000 150000
aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcdeaa...

output:

58046174517
12715251464
5723988017
161223697602
137002400916
30563623878
98934054385
59077629445
113925111785
28840565698
156244390553
77320878352
59683981982
127942734209
121145579565
87520380292
55236806101
2117874653
80900981342
31724248103
50230142282
711792462
83498404152
29926218182
8820224616...

result:

ok 150000 lines

Test #15:

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

input:

1000 150000
aabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcd...

output:

43966954106
63457970792
261177599185
84416298978
32467601340
158024435898
129927481955
29905035826
1663395309
262974056170
126552502741
3977985830
6794527980
134076085617
153168175752
20202212393
20413397242
263088231784
188742026136
2338731931
31903630853
144258078247
11137714967
22338312083
194691...

result:

ok 150000 lines

Test #16:

score: 0
Accepted
time: 219ms
memory: 44360kb

input:

150000 150000
aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcde...

output:

29914293876821
29388248888943
5520238628990
6509772252533
11376377552909
901817826019
13219593022192
23330308156488
33721084055601
10522195135985
1748546656146
1553205391001
15793344985123
33174193324692
26957558511532
8590975656478
7024857425105
14444339872596
2023167053405
5779413699241
2334817520...

result:

ok 150000 lines

Test #17:

score: 0
Accepted
time: 211ms
memory: 45428kb

input:

150000 150000
aabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaaba...

output:

51654672077087
18128065265954
10648077478275
24096372633749
33921372063966
52844542543234
19475889095501
49998404687384
30981572147127
53639263941544
7723904914977
3305784882722
36334815617245
36978590959883
39392351303785
33813693293258
7380058627592
17560621637115
9885403408272
14150106810987
2507...

result:

ok 150000 lines

Test #18:

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

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

813092418312696
1317798689473715
1315665465011076
2405711931597
356128071216857
204530268744615
796004029533782
2524560020845716
2142315805349726
1000649874336585
3110164476348575
2074236435764977
869887553468426
135346186547404
2107116066259453
1409642986095650
923200979353524
376619890608622
17975...

result:

ok 150000 lines

Test #19:

score: 0
Accepted
time: 362ms
memory: 44168kb

input:

150000 150000
aabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaab...

output:

891232692268242
180239781074503
762986955623910
2182769025630738
892305971824847
911080210251582
1273751943749997
1612958343425903
839270032556736
1812514937518138
2753082659282112
1273772162515030
1359136888087723
2843461425942221
1848164748961046
601261559736813
12298394517162
882181981558879
2969...

result:

ok 150000 lines

Test #20:

score: 0
Accepted
time: 405ms
memory: 45084kb

input:

150000 150000
aabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaab...

output:

1194619495572
795884372512504
1175435646771188
2302482629192344
582273726204212
2236317824765870
119988076211482
678581408764964
2101023153383665
888572706609489
186359125426424
1397048595862182
1317852784077245
190253063244
865232742049445
1491695395427100
640644116246476
1446530862350308
170011517...

result:

ok 150000 lines

Test #21:

score: 0
Accepted
time: 323ms
memory: 44060kb

input:

150000 150000
aabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdeaabaabcaabaabcaabaabcdaabaabcaabaabcaabaabcdefaabaabcaabaab...

output:

432981642389138
369819684910697
674517425239465
595536647891124
177569847795803
934205515438256
182914252110569
3453242346130
379689140841865
472465468653933
551405636497734
924788388701343
387440477848840
403148807711424
118166293104989
231069344260660
455187760837014
654856703426747
14126165707025...

result:

ok 150000 lines

Test #22:

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

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

139092615923852
319712839391046
39921108996632
236395672026301
709843083668671
541581333895491
670629605184988
359722149795181
1434679507168815
427767149417380
103440733252864
162815973876064
5616565642136
213571238193114
473655044673898
1319021925607968
176177858522467
1094307268000496
789182609618...

result:

ok 150000 lines

Test #23:

score: 0
Accepted
time: 328ms
memory: 46932kb

input:

150000 150000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

176449221404353
857960219930710
842692900572808
32011407408076
36679450185285
77449627797994
773227897058900
242672941287399
112572896349484
1084073090765193
935389071307684
242262854116272
965264314963252
374225801426478
148690698579830
245286364056781
147691073049337
81763003844687
414872147677601...

result:

ok 150000 lines

Test #24:

score: 0
Accepted
time: 243ms
memory: 45860kb

input:

150000 150000
aabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcaabaabaabcaabaabaabcdaabaabaabcaabaabaabcaabaabaabcaabaabaab...

output:

75013838237868
17352127196790
18435593123029
59453124031842
69320849384091
17191835150296
10989209368636
11277496094302
49325334063534
82744384056372
50402212769634
77714097271276
24123534251919
1019327991978
9791176811923
45077398495657
16921358697596
46140159436459
87938135723225
51608242695868
31...

result:

ok 150000 lines

Test #25:

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

input:

150000 150000
aabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefgaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefaabaabcaabaabcdaabaabcaabaabcdeaabaabcaabaabcdaabaabcaabaabcdefghaabaabcaabaabcdaabaabcaabaabcde...

output:

51790349532872
51552703284865
51639707133662
51628954389848
51326994357282
51147387034925
51562168321876
51361004657199
51615987780988
51345690787679
51558502009159
51512388090741
51446130081472
51424934077872
51530952726784
51279069272495
51541846195039
51394309708021
51769796479739
51763888860806
...

result:

ok 150000 lines

Test #26:

score: 0
Accepted
time: 73ms
memory: 44540kb

input:

150000 150000
aabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdeaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdaabaabaabcaabaabaabcdefaabaabaabcaabaabaabcdaabaaba...

output:

62738378528854
63240671067048
63109049690268
62930670790665
63128608767817
63154802293548
62903396261226
62691791732034
63072061751599
62678124397165
62854013020354
62810678615003
62432901249359
63266969650539
62868527107508
62984054065050
63323413497572
62820153495436
63041526771718
63072294192161
...

result:

ok 150000 lines

Test #27:

score: 0
Accepted
time: 77ms
memory: 44412kb

input:

150000 150000
aabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaabcaabaab...

output:

3685101344356853
3731861367894955
3751688492773431
3669019277489784
3728136168414795
3700443850676449
3692047336864334
3726615337010498
3732580406955496
3725834831382755
3756946026212108
3694602003701867
3711037467753390
3728247898408812
3756521839127576
3719104067223059
3695348388710118
37078393026...

result:

ok 150000 lines

Test #28:

score: 0
Accepted
time: 73ms
memory: 37976kb

input:

140000 150000
fxyviddixxstasofjeupbirusknnatlsgfekhgstmobjultzbnwmjewbqbkytmhchesjazdroxqmttlkpqokolalnpsptkxmuzytkimsnlnestfrmhtpkbwaznvkzlkwrnffhnucjdgmqnyefpsphxuqyebnczbtvtuwlcarbwlgnyzwmzjfvqrmhxoksqkxjutlrpdlaoseppwtmdnyepfqfygmwidklhpmkmhfytnuryjpztgcdrnzuzpfghnkhfscdlilfhheqwfuvpvbbusgwkkfcj...

output:

149487386057
113862413777
134923719940
23972844956
47659718599
139322041316
103615068534
18033539404
123080750859
32686113656
5606831184
57587094874
140892925172
186120371655
43492728874
76110450160
33616517940
11400279908
24389732424
24320716400
13997903903
45968029724
169420809364
81943765124
1018...

result:

ok 150000 lines

Test #29:

score: 0
Accepted
time: 73ms
memory: 37556kb

input:

150000 140000
qbagrggaowomatohfbgfglmelgpqgaqucijajgdhahzbpkpbkdqjyahjdenjfshmwhagkyjjszwuuswgpftghjtaogfffprhfhjiuwoigccgljccfhaihzagxswwfwusgswgggvjgfkfsntadaeafwshehnjwqwjgzkhebcggdhdsaafwehnjjwxgjfatxenkawzggfgxaavhjjkiflslegagehhhlkhgfapywyohexgfsxgawhdwdvhikswhfujwkgfojyshurcjnjghkhjsapdaadlff...

output:

41516161172
46091924632
36038323677
32196508911
19063468322
26836664454
13365203988
4215343027
16603596694
26910364649
6231712322
22129521478
34864597882
3182673144
60064960957
3130370755
17022957794
2006692899
31573229932
41465818542
37099154716
784864665
7224205839
41188101845
14389274943
25328998...

result:

ok 140000 lines

Test #30:

score: 0
Accepted
time: 0ms
memory: 28192kb

input:

1000 1000
yaaaaaaaaaaaagcaaaawbaawvaanaatptaaavakbaapmaqpmaaaameliakuaaaaaaafaaagaaaaaaaamalmajzakaacaaaiqqsfaaaaaamaaaaaajsaoajndafaaxahsaeaohqaoaaaaakmuqaaaayaaemalaamdaajaswaahawazaaaaakbgaaaqvaaiaabaniarauqaauamasadaaacxuazazaacaalapfaauaaalaaaavaaazaaaeacaaaaaxcalanaayzbxaaasalaasascaaaiaojaoav...

output:

370947276
234083642
402828548
15940636
81279372
0
452226648
0
0
15940636
386887912
97220008
0
81279372
0
81279372
15940636
15940636
686310290
234083642
386887912
81279372
81279372
386887912
234083642
686310290
702250926
234083642
386887912
152804270
605030918
15940636
686310290
97220008
686310290
15...

result:

ok 1000 lines

Test #31:

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

input:

150000 150000
jaapljaaadaaanasaeaaoaognyaatmgalaaaaajxaiahbaaauaauaairmyafhaoadaaaaaaaqaaeuaaacaaaueaaadaaaaaaaaqaaaaaaawacmraaaahapataaafmaaaaaxyahaazaajaalauhaatataibaayrhrxsmdsagaaaummymaaahmuaaaaaaaaaroxaayayaowtatyiaqvuahaoraavaaaaaacaaeaaearsdaafnajapaaaazaaaakcaazauladadnawaacazadeaaajahuiaqa...

output:

22819398310
24739907040
8629836374
23359395577
25736223491
15601539213
337784025
26174757748
11031343766
13328039385
10599601370
4093075630
13617636157
19709610870
3695394555
59620636021
43913032248
6612358951
13591313025
54649080650
19363465811
53924566117
21631188613
56653211225
32260240456
188007...

result:

ok 150000 lines

Test #32:

score: 0
Accepted
time: 98ms
memory: 46304kb

input:

150000 150000
abaaaaaaaabaaaaayaaaaaaaaaaabaaaaaaaaaaaaaaxaaaaaabaaaaabxaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaayaaaaaaaaaaaaxaaaaaaaaaaaaaaaaaaaaaaaaaaayaaaaaazaaaaaaaaaaaaaaaaaaaaayaaxaaaaaaaaxaaaaaaaaaaaaaaaaaaayazaaaaaaaaaaazaaayaaaaabaaaaaaaaaaaaaaxaaaazaaazaayaaaaaz...

output:

2109154320691
1811295536184
1305874457798
1317480361367
3346830806215
1128585436673
2216669793859
876865837240
86073235223
298200815338
643988134846
1222094437721
2957947755668
362298850167
1482640156064
8210951856
1241506533511
1772927272097
215982589051
3107347387217
1316468548824
592284705655
435...

result:

ok 150000 lines

Test #33:

score: 0
Accepted
time: 21ms
memory: 28084kb

input:

1000 100000
abaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaabaaba...

output:

74798182608
157149465127
2105912190554
7460151149192
2268723395246
785956239210
435305709
2139278991147
1940216181949
88942985436
2872764543
2641374260497
400109478286
9690480277
2520126745257
341835162638
48689008059
25869193402
1079663008688
1652926212032
60415582650
5275716859677
46261753181
6122...

result:

ok 100000 lines

Test #34:

score: 0
Accepted
time: 21ms
memory: 24456kb

input:

1000 100000
xyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxyxyyxyxxy...

output:

149618841838
127864948561
54980335836
2543732655737
29119803604
111349757
2906360068619
89391907823
18211368590
501376038870
204593996945
311948130943
2532217668941
131848782598
514249430797
1064992254691
4007581664
1281829072352
2401926804764
537641132330
1985460140773
4940514023
1158980874786
2899...

result:

ok 100000 lines

Test #35:

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

input:

1000 100000
qisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqisndqis...

output:

21743525132
2955679216579
142037109397
2808408913
183591971539
6035807926
1494265886855
111297641344
1751001849910
3192836139804
327654195802
1160271229172
155937740395
1233464278387
1071083667110
1413311998306
2362202307428
481043470961
855655615673
544719653451
1169701118795
340343809683
326585994...

result:

ok 100000 lines

Test #36:

score: 0
Accepted
time: 719ms
memory: 51384kb

input:

150000 100000
ppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppppoppp...

output:

5592411450636753
135209829168391
49971109943102794
53150618284444849
32780298792197527
19668912700554961
3991295085690853
18121009996940124
1958502246040
348589459090434
6776793053734199
12667221050171100
71564981250810601
18728832441138479
14622207012817546
3781076536750452
699462977097104
43814745...

result:

ok 100000 lines

Test #37:

score: 0
Accepted
time: 698ms
memory: 47144kb

input:

150000 100000
tuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuututtutuutut...

output:

6029367874134384
14727991674637894
65528086805063
22262151197411199
13290008685433206
2216964586470248
35406020927137844
1288253206474488
122891953188100
15264445721996291
29769592090200819
54137147358694338
7064714568738187
13410090337383781
627494366583965
13119401523472213
18180772800585677
52023...

result:

ok 100000 lines

Test #38:

score: 0
Accepted
time: 698ms
memory: 50680kb

input:

150000 100000
eeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeoveeeeeeove...

output:

660831893107150
852808508854170
25640865201842134
25858072792291872
61941952435199838
908296187754135
2190825954865481
12616603141014603
82649938049438
19574710854186724
18034029154050399
1743413410707578
1357830351826691
314778001830398
13442605730145814
34098282799367830
1152318337535
958861617983...

result:

ok 100000 lines

Test #39:

score: 0
Accepted
time: 818ms
memory: 49812kb

input:

150000 100000
ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab...

output:

165193773150972023
1538088247569916
4077205028456474
64723160256828206
2879737616493342
13988682177623338
1022122245821095
47170492343166
69608730493211757
1084502483630793
563841093144006
13869016628394731
47897597658524539
88684322723491811
144432621254952409
117406025890040120
102915388576218776
...

result:

ok 100000 lines

Test #40:

score: 0
Accepted
time: 749ms
memory: 48796kb

input:

149997 100000
abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabca...

output:

67598779861293222
36679538821933591
97698919357542782
15562591771418340
150553368460367
36980407863203108
4721746574275749
19110290707850782
107878608681437900
7604576038087844
7454079795245705
2408114454060810
200597787236533
751653612398308
12704990794626612
38180346177625555
14678791090778118
113...

result:

ok 100000 lines

Test #41:

score: 0
Accepted
time: 69ms
memory: 45712kb

input:

150000 100000
abcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdabcdab...

output:

138815215004022364
136361480020059660
137825902967695584
136313477499374331
134936003862446073
138149079107680312
137718268796572322
138746298238989081
137514238486868146
137549472707128014
134700961073280182
136494453652604168
136681098339708958
138400088399748010
138344288809278195
136485214236642...

result:

ok 100000 lines

Extra Test:

score: 0
Extra Test Passed