repeat

Consider a sequence of characters T, and k a non-zero positive integer.

Task

Determine a subsequence of sequence T made up of k consecutive characters that is repeated in the sequence a maximum number of times.

Input Data

Input file repeat.in contains two lines. Line one contains sequence T, and line two contains positive integer k.

Output Data

Output file repeat.out will contain two lines. Line one will contain a positive integer Rmax, representing the maximum number of repetitions in sequence T of the determined subsequence of length k. Line two will contain the start position of a subsequence of length k that is repeated in the sequence Rmax times. Of all start positions, the smallest one will be displayed.

Constraints and Statements

0 < k <= 500
Sequence T is made up of maximum 100000 lowercase English alphabet letters.
Two distinct appearances of the subsequence may partially overlap.
Positions in sequence T are numbered beginning with 1.

Example

repeat.in	repeat.out	Explanation
ababacabac 3	3 1	Subsequence of length 3 aba is repeated a maximum number of times (3). The minimum start position is 1.

Time limit: 2 seconds/test

prof. Marinel Serban
"Grigore Moisil" Iaşi IT High School
Contact:marinel_serban@yahoo.com