Most Frequent Subsequence

Given a string s and an integer k, you are required to find the contiguous subsequence of length k that appears most frequently in s. In case there is a tie in the frequency, the lexicographically smallest subsequence should be returned.

For example, consider the string s = "aabbcc" with k = 2. The possible contiguous subsequences of length 2 are "aa", "ab", "bb", "bc", and "cc". Here, "aa" appears once, but it happens to be the lexicographically smallest among those with the highest frequency.

The problem can be mathematically described as follows:

Given a string \( s \) of length \( n \) and an integer \( k \), for each \( i = 0, 1, \dots, n-k \), let \( s_i = s[i:i+k] \). Let \( f(\sigma) \) be the frequency of a subsequence \( \sigma \). Find a subsequence \( \sigma^* \) such that \[ \sigma^* = \min\{ \sigma : f(\sigma) = \max_{\tau} f(\tau) \}, \] where \( \min \) denotes the lexicographically smallest string.

inputFormat

The input is read from standard input (stdin) and consists of two parts:

1. A single line containing the string s.
2. A single line containing the integer k.

You can assume that the length of s is at least k and that s contains only lowercase letters.

outputFormat

Output the most frequent contiguous subsequence of length k from s to standard output (stdout). If multiple subsequences have the same maximum frequency, output the lexicographically smallest one.

aabbcc
2

aa