Description
Problem brought to you by NTHU Order a Rabbit club.
On her birthday, Chiya received a fabric of N cm from her friends, and she wants to make a kimono out of it.
The fabric has up to 26 different colors of flowers on it, and every centimeter of it has exactly one flower. She will cut exactly one continuous segment from it, and for aesthetic reasons, she will only cut at some integer number cm.
Yet again for aesthetic reasons, she wants the fabric for kimono to be K-partite for her favorite number K. A piece of fabric of M cm can be represented as a string S of lower-case latin letter, and it is K-partite if it satisfies the following conditions:
(1) the length is at least K
(2) the fabric can be partitioned into exactly K non-empty contiguous segments of the same color, with each pair of neighboring segments having different colors.
For example, the strings “aaabbbccc” and “ggoogg” are both 3-partite. The partitioning are as follows:
aaa | bbb | ccc
gg | oo | gg
While the string “wwwwwaaa” is not 3-partite.
So given the fabric "abcdccgggk" and K=2, Chiya has the following choices of cutting out a K-partite segment:
1. [ab]cdccgggk
2. ab[cd]ccgggk
3. abc[dcc]gggk
4. abcd[ccgg]gk
...
Chiya wonders what is the lengths of the longest and shortest K-partite subsegment she can cut out from this fabric. (Since you are from CS town, she knows you can solve this within a minute.)
A picture of Chiya to cheer you up:
Input
The input file contains two lines. The first line has 2 integers N and K, while the second line has a string of length N, consisting of only lowercase latin letters.
The whole string is guaranteed to be X-partite for some X>=K, so that the answer always exists.
1 <= N <= 5*105
Output
Output two integers L1 and L2: the longest and shortest lengths of a K-partite subsegments.