QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#630917#9425. Generated StringZhangYiDeAC ✓310ms61460kbC++237.6kb2024-10-11 20:56:392024-10-14 17:50:39

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 14004kb

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: 4ms
memory: 10604kb

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: 4ms
memory: 10624kb

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: 4ms
memory: 10236kb

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: 152ms
memory: 26868kb

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: 208ms
memory: 46828kb

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: 272ms
memory: 41948kb

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: 180ms
memory: 33780kb

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: 263ms
memory: 42660kb

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: 218ms
memory: 47688kb

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: 204ms
memory: 40724kb

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: 156ms
memory: 31624kb

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: 244ms
memory: 36316kb

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: 166ms
memory: 30556kb

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: 2ms
memory: 16584kb

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: 277ms
memory: 50724kb

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: 228ms
memory: 55084kb

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: 269ms
memory: 51560kb

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: 289ms
memory: 53220kb

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: 258ms
memory: 61460kb

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: 310ms
memory: 51580kb

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: 203ms
memory: 37488kb

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: 166ms
memory: 38636kb

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: 125ms
memory: 32620kb

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: 221ms
memory: 37300kb

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: 127ms
memory: 37724kb

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: 224ms
memory: 33988kb

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: 275ms
memory: 57876kb

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