Most Frequent Substring

You are given a string s and an integer k. Your task is to find the most frequent substring of length k in s. In case of a tie (multiple substrings having the same maximum frequency), return the lexicographically smallest substring among them.

Note: The substring is defined as a contiguous sequence of characters in s. The input string consists of printable characters and k is a positive integer such that k ≤ |s|.

Example:

Input:
abcabcabc
3
Output:
abc

</p>

inputFormat

The input is given via standard input and consists of two lines:

1. The first line contains the string s.
2. The second line contains the integer k.

outputFormat

Output the most frequent substring of length k in s. In case of a tie, output the lexicographically smallest substring.

## sample

abcabcabc
3

abc