Maximizing Frequency with Replacements

You are given a string s of length n consisting of lowercase English letters and an integer k. You can replace at most k characters in the string with any other lowercase English letter. Your task is to determine which letter can achieve the maximum frequency in any contiguous substring after performing at most k replacements. In case of a tie (i.e. several letters can achieve the same maximum frequency), return the lexicographically smallest letter.

More formally, for each letter \( c \) from 'a' to 'z', you are allowed to choose a contiguous substring of s and change some characters (at most k of them) such that all characters in that substring become \( c \). Let the maximum length obtainable in this way be \( L_c \). You need to output the letter \( c \) for which \( L_c \) is maximized. If there is more than one such letter, output the smallest one in lexicographical order.

Example:

Input:
8
abbcccaa
2
Output:
c

</p>

inputFormat

The input is given from stdin in the following format:

1. The first line contains an integer n, the length of the string.
2. The second line contains a string s of length n consisting of lowercase English letters.
3. The third line contains an integer k representing the maximum number of characters that can be replaced.

outputFormat

Output a single lowercase English letter to stdout which is the answer to the problem. If there are multiple possible answers, output the lexicographically smallest one.

## sample

8
abbcccaa
2

c

</p>