QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#641739#9425. Generated Stringucup-team5077AC ✓1416ms90816kbC++146.3kb2024-10-14 22:57:592024-10-14 22:57:59

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 59228kb

input:

8 7
abcaabbc
+ 3 1 3 2 4 3 8
+ 2 1 4 1 8
+ 1 2 4
? 1 5 6 1 7 8
- 3
+ 1 2 5
? 1 2 3 1 5 5

output:

2
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 11ms
memory: 59440kb

input:

5 2000
bbaab
+ 1 3 5
+ 2 5 5 3 5
- 2
? 1 1 3 3 3 3 4 5 2 5
- 1
? 3 1 1 2 4 1 5 1 3 4
? 1 1 2 2 2 4 4 4
? 1 1 5 1 5 5
+ 3 1 2 1 5 1 4
? 2 1 5 1 3 2 1 2 5 5
? 1 3 4 1 4 5
- 9
? 1 1 4 1 2 3
+ 2 1 5 1 2
+ 1 1 4
- 15
- 14
? 2 2 5 2 5 1 3 4
+ 1 2 3
- 19
+ 3 1 4 1 5 4 5
- 21
+ 1 2 5
? 3 1 5 5 5 1 5 1 3 5
?...

output:

0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
2
0
3
1
0
0
0
0
1
0
0
0
0
0
0
0
0
2
0
0
0
0
0
1
0
0
0
0
0
0
0
3
1
0
1
0
2
0
0
0
3
0
1
0
0
2
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
2
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
1
0
0
0
1
3
2
3
0
0
0
0
0
2
0
0
2
0
0
0
2
3
...

result:

ok 702 lines

Test #3:

score: 0
Accepted
time: 7ms
memory: 55452kb

input:

5 2000
ababa
+ 1 4 4
+ 1 2 2
? 1 1 2 2 3 3 3 3
? 2 3 3 1 2 1 3 4
+ 2 3 4 2 2
+ 1 3 3
+ 1 2 2
+ 1 1 2
- 7
- 1
- 2
? 2 4 4 3 3 2 2 2 4 4
- 5
+ 1 1 1
- 6
? 1 3 4 2 1 2 4 5
+ 1 4 5
- 17
? 2 1 1 1 2 2 1 1 1 2
- 8
+ 2 3 4 2 3
+ 1 4 5
+ 1 2 3
+ 1 3 4
- 21
+ 1 3 3
? 1 1 2 1 4 4
? 2 1 1 4 5 1 5 5
- 24
- 22
?...

output:

0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
2
0
3
1
0
1
0
0
2
0
0
2
0
2
0
3
3
2
4
0
0
0
0
0
0
4
0
0
4
2
1
1
0
0
1
3
2
0
0
0
2
2
0
2
0
0
0
0
0
1
0
3
1
1
0
2
9
0
1
1
1
0
5
8
1
1
1
0
0
5
4
4
4
6
6
0
6
6
1
5
0
3
5
1
0
0
1
8
0
5
0
5
0
3
0
0
0
1
0
1
1
1
1
1
0
0
0
1
5
2
0
2
6
5
1
4
0
0
7
0
2
6
1
5
0
5
0
9
0
0
0
0
1
0
0
...

result:

ok 647 lines

Test #4:

score: 0
Accepted
time: 8ms
memory: 59520kb

input:

5 2000
bbaba
+ 1 3 3
- 1
+ 2 2 2 1 1
- 3
+ 1 4 4
? 1 3 3 1 2 2
+ 2 2 2 1 1
- 5
? 2 4 4 1 1 2 3 3 3 3
- 7
+ 1 5 5
+ 2 2 2 2 2
+ 1 5 5
- 11
+ 2 2 2 1 1
? 1 3 3 1 2 2
+ 1 1 1
+ 1 2 2
+ 1 3 3
- 17
- 19
+ 1 1 1
+ 1 3 3
? 1 3 3 1 3 3
+ 1 5 5
? 1 4 4 1 4 4
- 22
+ 1 5 5
+ 1 1 1
? 2 5 5 3 3 1 1 1
? 1 5 5 1 1...

output:

0
0
0
2
4
0
0
2
5
0
4
0
1
8
0
0
1
6
0
4
7
0
2
0
4
0
0
0
6
1
1
0
0
6
0
9
1
7
0
1
1
0
0
1
7
1
0
1
2
9
0
1
2
2
0
0
2
7
0
4
2
8
2
8
0
1
0
2
0
9
10
1
1
2
1
1
0
0
10
0
0
0
6
0
0
2
4
0
5
4
5
5
5
0
4
0
3
2
2
5
5
5
5
0
0
0
4
0
3
5
5
6
9
6
6
4
6
0
4
6
0
4
4
2
2
12
0
5
6
6
6
13
0
13
2
1
0
1
10
10
5
8
1
8
8
1
1...

result:

ok 672 lines

Test #5:

score: 0
Accepted
time: 395ms
memory: 78132kb

input:

5 100000
bbabb
+ 1 2 5
? 5 4 5 3 5 4 5 2 4 4 5 3 1 5 3 4 3 4
? 2 4 4 1 5 1 1 3
? 1 3 5 5 1 1 1 3 1 1 4 4 3 5
? 1 2 5 2 2 5 2 5
+ 2 1 5 3 3
- 1
+ 4 1 5 1 5 1 5 2 3
? 4 3 5 1 5 1 5 2 5 1 2 4
? 1 1 5 3 4 4 3 4 1 5
- 6
- 8
+ 2 1 5 1 4
- 13
? 1 1 5 3 1 2 3 4 1 3
+ 5 2 4 1 2 1 4 2 2 1 5
- 16
+ 1 1 5
- 18
...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
4
0
3
0
0
0
1
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
2
0
8
0
0
0
0
0
0
0
2
0
0
...

result:

ok 33212 lines

Test #6:

score: 0
Accepted
time: 874ms
memory: 78876kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
1
0
1
0
1
0
5
0
4
1
1
1
1
2
0
3
0
0
0
0
1
1
0
0
2
2
0
0
1
5
1
0
0
3
3
5
2
5
0
8
2
2
2
13
2
2
0
2
4
11
9
5
3
14
4
9
19
12
4
12
11
6
7
8
2
22
7
3
20
7
9
6
0
5
5
17
2
9
9
0
2
7
10
11
0
9
3
4
5
12
6
10
0
2
21
2
9
1
3
1
2
2
10
22
8
21
4
3
16
3
8
2
12
9
0
2
12
4
5
19
16
7
5
4
4
3
8
5
11
4
6
5
13
0
6
5
1...

result:

ok 33583 lines

Test #7:

score: 0
Accepted
time: 632ms
memory: 80972kb

input:

100000 100000
baabbabaabaaaabbaaababaaabbbbbaabbababbabbbaabbaaabbbbababaababbbbbababaabaaabaaababaabbbbaaababbbbabaabbaaaaaabbbabbbabababababaabbabbbbbaaabababbbaabababbbaaababaabbaaaabbabbaabbababaabbaaaababaabbbbbababbaaabbbaababbaaaaaabbbbabbbbbbabbaabababbbaaaaaabbabbabaaaaaabbbaaaaaabaabaaabab...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 33381 lines

Test #8:

score: 0
Accepted
time: 633ms
memory: 80964kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

2
2
0
2
1
1
2
2
2
2
0
0
0
0
0
1
0
0
1
0
0
0
2
2
2
0
1
0
0
0
0
1
0
2
3
0
1
0
1
0
0
1
1
2
2
2
1
1
1
0
0
0
2
0
3
0
0
0
0
0
1
2
0
0
1
1
0
0
0
1
1
2
0
2
1
2
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
2
2
1
2
4
3
2
0
2
0
0
1
4
0
0
1
1
5
1
0
1
0
0
2
1
0
3
3
1
0
1
1
2
2
3
0
1
3
7
6
0
7
1
1
1
5
2
5
0
2
6
2
2
2
5
...

result:

ok 33565 lines

Test #9:

score: 0
Accepted
time: 819ms
memory: 79116kb

input:

100000 100000
aaabbbabbaababbbbbbaaababbbaaaaaabbaaaabababbabababbabbabbbaababbbbabaabaaabbaaabbabababbaaabbabbaaaaabbabababbaaaaababbbbabbabaaabbbaabaabbbaaababbbbbabaaabaaaaabbaabaabbabababbabaaabbbbbbbbaababaabbbabaabbabaaabbbbbababaaabbbbbaaaaaaabbbabbbaabbaabbaaaaaaabbbaabbbaabbaaaababbabaababb...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 33118 lines

Test #10:

score: 0
Accepted
time: 887ms
memory: 79004kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
1
0
0
0
2
0
0
0
0
0
0
0
1
0
0
1
0
0
3
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
4
0
1
0
0
0
0
2
0
3
4
4
5
8
7
9
5
0
9
3
8
2
9
0
5
7
1
7
9
0
1
4
1
5
8
5
1
0
0
5
0
4
12
0
9
5
11
10
3
1
8
1
9
2
1
0
5
5
5
0
2
5
1
1
0
0
12
8
11
11
1
4
11
10
3
7
9
9
4
12
11
5
9
6
1
2
8
10
11
4
17
11
6
3
2
4
1
1
3
1
3
2
3
6
5
4
8
12...

result:

ok 33215 lines

Test #11:

score: 0
Accepted
time: 936ms
memory: 82992kb

input:

100000 100000
mwtmtwnsgaynckkprtjhfnmyzylblnkmrismcyyksqxcikyhrsannbmflvloshydnfvydmuoyphxpjgxsfmyqozidivsigleuvmnyniccdqjekyzjtytudpjbwjmsulfipurvjuxququmkfbrigctewalryoiilmqapofcwpllcwjnzmbtirmfmyhbuqkwqhzidrqbxnulklkjmrnzzclykjoflrbimnshtruucmjiukgvzoekyjnjpkkpwcgrbidyuyodlqaaywfsnbcczuxwsbnrcprq...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 33475 lines

Test #12:

score: 0
Accepted
time: 379ms
memory: 82020kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
0
1
1
1
1
3
1
3
4
3
3
4
5
7
4
4
4
5
3
4
6
1
0
4
4
12
3
9
9
9
3
7
10
6
9
2
9
4
8
8
7
4
7
7
6
1
5
6
6
4
5
4
3
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
1
1
0
2
0
0
0
0
0
0
0
0
0
0
1
0
1
1
3
1
1
1
4
4
1
0
4
3
2
0
2
1
0
0
0
0
6
5
0
2
4
2
0
0
0
0
1
0
1
0
0
0
2
4
4
1
3
5
1
0
0
0
0
0
0
2
2
2
0
0
0
0
0
0
0
0
2
2
3
1
...

result:

ok 33689 lines

Test #13:

score: 0
Accepted
time: 508ms
memory: 79648kb

input:

100000 100000
bbbbbaabbbbbaaabaabaaabbbbaabaaabaabbababbaaaaaaaabbababbbbabbababaabbabaabbaaaabbbbabaabbababbbbbbbaaabaabbabbbbbbaaaaababaaabbbabbaabaabaaabbbabbaaabaaaababbaaabaabbabaaaaaaababababbbbaabbaaaabaabbbbaaaababbabbbbabaabbbaaabbbaabaaabbbaaabaabbbbbabbaaabbaabbabbaababbbabbababbabbaabbbb...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 33438 lines

Test #14:

score: 0
Accepted
time: 245ms
memory: 77312kb

input:

100000 100000
aaabbbbabbaababbabaabbabababaaaaabbababababaabbaaabbbaaaaaabaaabbabbabbbabaabbaabbabbbbbbbaabaaababaaaaabaaaabbbaaaabbaabbaabbbbaaababbabababbaaaaabbbababababaabaabababbabbbbbabbabbbbaaababbbbaabbaaabababaabbbaaabaaaabbabbaabbbaabbbbabbbababbbabaabbaababaaaabbaabaaabbaaabaaaaabbbbbbbab...

output:

0
0
0
0
0
0
0
2
1
4
0
0
1
1
0
0
0
2
0
0
0
8
2
0
2
0
0
0
0
0
0
7
0
0
0
0
10
5
4
4
0
1
4
0
0
2
4
4
0
0
0
6
0
4
0
0
0
7
4
7
3
5
0
0
0
7
0
7
7
0
8
7
3
0
0
11
0
0
4
11
0
2
2
0
11
9
2
11
3
2
12
3
0
13
0
0
3
0
4
5
0
0
0
4
6
0
0
6
0
4
4
0
0
0
5
5
0
0
6
0
7
0
7
8
7
0
6
6
7
7
7
6
17
6
8
7
7
3
15
0
14
6
0
0
14...

result:

ok 33321 lines

Test #15:

score: 0
Accepted
time: 8ms
memory: 55240kb

input:

5 1000
glbdh
+ 2 2 2 1 2
? 2 1 2 3 4 1 1 5
? 1 3 4 3 2 3 4 4 1 5
- 1
? 1 1 2 2 1 2 1 4
+ 1 1 3
+ 2 1 4 1 2
? 2 4 5 1 2 3 2 3 3 4 1 2
? 2 4 4 1 1 2 3 4 1 3
? 1 1 2 1 1 3
- 7
+ 1 1 5
? 1 3 3 1 1 2
? 3 3 4 4 4 2 3 1 1 2
+ 3 1 5 2 5 1 2
? 1 1 1 3 1 2 3 3 1 2
? 2 4 5 3 3 2 3 3 1 2
? 1 2 3 2 3 4 1 2
? 1 1...

output:

0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
0
0
1
0
0
0
9
0
0
0
0
3
0
1
0
1
0
1
11
0
0
11
0
0
0
0
0
0
12
0
12
0
0
1
0
0
1
0
0
0
0
0
0
0
11
0
0
0
0
0
0
0
3
0
0
13
0
0
0
0
13
0
0
0
0
0
1
0
0
0
0
0
0
5
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 525 lines

Test #16:

score: 0
Accepted
time: 1134ms
memory: 84308kb

input:

100000 100000
mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmm...

output:

0
0
0
1
0
0
0
2
0
0
0
0
2
0
0
0
0
1
0
0
2
0
0
1
1
1
1
0
1
2
2
0
2
1
1
1
0
2
1
1
1
1
1
1
0
2
3
3
1
1
1
1
4
1
3
4
0
2
2
2
2
3
2
3
2
0
2
1
3
4
4
3
1
4
2
0
0
3
2
3
3
3
2
3
0
3
3
3
3
3
5
4
0
4
3
4
3
4
4
1
3
3
4
5
4
5
1
6
5
6
8
6
3
6
8
6
3
5
2
1
6
4
3
6
3
1
1
3
4
3
5
8
4
3
5
6
3
6
1
7
3
7
8
6
4
7
4
3
1
5
...

result:

ok 49940 lines

Test #17:

score: 0
Accepted
time: 1246ms
memory: 87252kb

input:

100000 100000
dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd...

output:

0
6
5
7
5
8
6
6
17
13
14
20
26
23
16
21
20
17
39
26
31
32
46
39
36
52
36
28
28
28
26
29
46
53
48
55
18
43
44
40
49
25
59
42
57
60
42
36
65
50
52
59
25
56
42
42
16
77
43
42
65
57
57
52
44
48
42
19
43
72
65
56
101
69
37
69
73
106
72
55
66
22
70
60
40
73
81
78
60
79
94
63
74
62
74
78
110
76
107
113
108...

result:

ok 9964 lines

Test #18:

score: 0
Accepted
time: 1226ms
memory: 86536kb

input:

100000 100000
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...

output:

0
0
1
1
0
0
0
2
2
0
0
1
2
2
0
0
3
3
3
2
0
1
3
0
1
0
2
1
1
1
2
5
4
3
4
3
3
1
3
1
2
1
5
2
3
2
3
5
2
5
3
1
5
3
1
3
1
1
2
4
4
1
5
1
1
2
3
3
3
4
2
5
3
2
2
4
4
2
4
3
3
5
4
7
4
8
6
8
5
4
4
4
6
3
4
7
5
4
9
6
6
5
7
7
5
6
6
5
5
5
6
8
6
5
5
4
7
4
7
4
4
5
4
5
4
8
4
4
5
5
4
8
4
8
8
8
4
7
9
5
7
6
7
6
6
6
8
6
10
6...

result:

ok 90061 lines

Test #19:

score: 0
Accepted
time: 1267ms
memory: 87860kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0
0
0
0
0
0
0
0
0
0
0
1
0
0
3
0
0
1
0
1
0
0
1
3
2
0
2
3
1
0
2
3
0
0
0
0
3
3
3
0
5
2
0
3
0
1
3
1
0
1
1
0
3
3
3
0
6
3
0
3
0
0
1
3
3
2
3
4
0
1
3
1
3
1
1
6
5
4
8
2
1
3
4
3
0
0
6
8
10
1
4
11
2
4
0
0
0
4
3
9
3
2
10
10
7
3
1
1
3
8
5
0
3
1
8
1
3
0
8
1
6
1
4
1
8
8
6
1
7
0
1
6
9
1
6
4
3
1
2
6
7
1
9
10
3
7
2
2...

result:

ok 49932 lines

Test #20:

score: 0
Accepted
time: 1416ms
memory: 89320kb

input:

100000 100000
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz...

output:

1
1
1
0
1
2
2
1
4
4
4
6
6
7
7
9
12
12
11
15
8
21
3
4
8
8
26
11
15
11
20
21
22
29
14
26
25
31
34
26
19
11
29
33
17
20
20
27
33
29
29
43
31
33
33
16
35
30
17
24
40
36
41
19
33
38
51
32
64
28
21
50
42
41
46
29
48
51
62
56
30
45
62
37
54
38
22
43
38
45
43
40
59
53
73
73
72
45
68
27
68
64
62
72
51
65
39
...

result:

ok 10030 lines

Test #21:

score: 0
Accepted
time: 1135ms
memory: 88236kb

input:

100000 100000
pppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
1
2
0
0
0
1
1
1
1
1
0
1
3
1
1
1
2
0
1
2
3
3
0
1
1
1
1
1
1
2
2
2
0
2
3
1
1
1
1
0
1
1
0
2
0
2
0
1
0
2
3
2
1
1
1
1
1
5
3
0
2
2
2
0
2
2
2
1
2
4
5
2
2
5
2
1
2
5
0
2
5
3
5
5
0
2
2
3
0
4
2
4
0
2
1
2
1
2
2
1
0
2
1
3
1
0
2
0
2
2
0
3
3
3
5
2
2
5
3
6
5
3
3
...

result:

ok 90160 lines

Test #22:

score: 0
Accepted
time: 721ms
memory: 84672kb

input:

100000 100000
faxyuxswncplvrzynzvlbjqvkdhqfmdddimahxygchjxwqaouebuiijkydypsvhlqeoelcnizmzcnuzvxzqilitcmbrhwjtbastbqyktczoarrihswnbsjtzvkrdjkwzijqkcziwqndcfgyvpepsokrgtlvrwxwjbtctdluemgbpzneomxcqdxxaoxdrgdzrherrygznacprcimyudgbjpelkpxotckckzihjuxnlmkczsutackpunsfnkwvhkadjfnhmvplqfgzmkssoacpuxaipepwro...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
2
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
...

result:

ok 49806 lines

Test #23:

score: 0
Accepted
time: 656ms
memory: 85960kb

input:

100000 100000
twdczjujsjrmpsipsunndczjujsjrmpsipsuwynwdczjujsjrmpsipsuwjwdczjujsjrmpsipsuyhtwdczjujsjrmpsipsuwwddczjujsjrmpsipsudczjujsjrmpsipsuybtwdczjujsjrmpsipsuwexdczjujsjrmpsipsuwevtwdczjujsjrmpsipsuwexatwdczjujsjrmpsipsuapwdczjujsjrmpsipsuwepwdczjujsjrmpsipsuwowdczjujsjrmpsipsudczjujsjrmpsipsu...

output:

0
1
0
0
0
1
0
0
1
1
7
0
0
0
0
3
3
0
3
3
1
1
0
0
0
0
0
3
9
13
0
14
5
0
2
10
6
5
2
9
3
9
3
5
6
2
1
0
4
2
1
0
0
10
3
5
2
0
7
0
30
27
0
3
13
0
0
0
1
0
22
0
0
1
0
0
27
0
35
1
0
1
17
0
0
0
1
10
0
0
0
2
2
15
0
52
0
4
14
0
0
36
6
0
25
0
12
0
6
1
0
1
0
0
0
3
9
2
0
60
38
16
15
11
0
0
0
2
13
0
0
6
0
7
0
0
0
25...

result:

ok 9909 lines

Test #24:

score: 0
Accepted
time: 320ms
memory: 85456kb

input:

100000 100000
gqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxicygqxi...

output:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
3
3
3
3
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
4
5
5
5
5
5
6
6
6
6
7
7
7
7
7
7
7
8
8
8
8
8
8
8
8
8
8
8
9
9
9
10
10
11
11
11
11
11
11
11
11
12
12
12
12
12
12
13
13
13
13
13
13
13
14
14
14
15
15
15
15
15
1...

result:

ok 90066 lines

Test #25:

score: 0
Accepted
time: 713ms
memory: 87004kb

input:

100000 100000
nbaiostoyrvtrkngnuatnddlyjzqnfgufkqtmahrkmxxstxnqszjxibrnymsyujvzvazdmernpfoapfefjnbberzsmfmfqjwyyrqmbgdzppkratnddlyjzqnfgufkqtmahrkmxxstxnqszjxibrnymsyujvzvazdmernpfoapfefjnbberzsmfmfqjwyyrqvazynjzqnfgufkqtmahrkmxxstxnqszjxibrnymsyujvzvazdmernpfoapfefjnbberzsjzqnfgufkqtmahrkmxxstxnqsz...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

ok 50106 lines

Test #26:

score: 0
Accepted
time: 485ms
memory: 90816kb

input:

100000 100000
avrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpogavrzpo...

output:

2
2
13
28
31
64
83
95
108
119
121
127
134
141
157
158
162
164
175
181
181
195
201
201
209
210
215
218
253
259
263
263
273
274
280
303
310
317
318
325
328
342
360
368
376
392
393
420
427
431
434
440
456
457
485
501
502
533
556
593
601
601
605
606
614
617
644
654
687
700
721
723
728
728
731
731
738
74...

result:

ok 9852 lines

Test #27:

score: 0
Accepted
time: 516ms
memory: 85892kb

input:

100000 100000
nzqcglfwczqmzqcglfwczazqcglfwczzmzqcglfwczzqcglfwczpmzqcglfwczzqcglfwcxmzqcglfwcznzqcglfwczqcglfwcmzqcglfwczmzqcglfwcjmzqcglfwczzqcglfwczrzqcglfwczqcglfwczqcglfwczmzqcglfwczwzqcglfwczqcglfwcjzqcglfwcmzqcglfwcmzqcglfwczzqcglfwcizqcglfwcomzqcglfwcmzqcglfwczzqcglfwcjmzqcglfwczmzqcglfwczmz...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
2
0
1
0
0
3
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
3
0
0
0
0
0
0
0
1
2
0
0
0
0
1
0
1
0
1
0
0
...

result:

ok 90005 lines

Test #28:

score: 0
Accepted
time: 1264ms
memory: 85344kb

input:

100000 100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

5379
21600
8676
17796
6561
7062
8794
24490
12428
13642
26349
12930
17230
4054
29012
19503
23951
2084
14612
6542
11110
18521
5532
30725
21338
30107
893
12051
20828
7845
32580
8063
4190
21112
8005
33480
15470
3466
1311
10240
13981
29868
3358
35905
19687
9180
46665
11173
4030
5610
14002
22315
28887
629...

result:

ok 49879 lines

Extra Test:

score: 0
Extra Test Passed