Most Frequent Substring

You are given a non-empty string s consisting of lowercase English letters and a positive integer k. Your task is to find the substring of length k that appears most frequently in s. In case there are multiple substrings with the same highest frequency, output the lexicographically smallest one.

For example, if s = "ababcabab" and k = 3, the substring "aba" appears most frequently, so the answer is aba.

Note: The input is taken from standard input (stdin) and the output should be sent to standard output (stdout).

inputFormat

The input consists of two lines:

• The first line contains the string s (a non-empty string of lowercase letters).
• The second line contains an integer k denoting the length of the substring to be considered.

outputFormat

Output a single line containing the most frequent substring of length k. If more than one substring has the maximum frequency, output the lexicographically smallest one.

ababcabab
3

aba