K-th Most Frequent Character

Given a string S and an integer K, your task is to determine the K-th most frequent character in S. The frequency of each character is determined by the number of times it appears in S. In case several characters share the same frequency, they are sorted in alphabetical order.

Note: The counting is case-sensitive and considers all characters in the string.

Detailed Description:

• Let freq(c) denote the frequency of a character c in S.
• All characters are sorted primarily in descending order by freq(c) and secondarily in ascending lexicographical order.
• The answer is the character at position K in this sorted order.

For example, if S = "aabbcc" and K = 1, each character appears twice, so the sorted order is a, b, c. Hence, the answer is a.

The mathematical relation can be interpreted in LaTeX as follows: For a given character \( c \), its frequency is \( \text{freq}(c) \). Sort the set \( \{ c: c \in S \} \) such that for any two characters \( c_1 \) and \( c_2 \):

[ \text{if } \text{freq}(c_1) = \text{freq}(c_2), \text{ then } c_1 < c_2 \quad \text{(alphabetical order)} ]

[ \text{Otherwise, } \text{freq}(c_1) > \text{freq}(c_2) ]

The K-th element in this ordering is the required answer.

inputFormat

Input Format:

1. The first line contains a string S.
2. The second line contains an integer K.

You should read the input from stdin.

outputFormat

Output Format:

Output a single character representing the K-th most frequent character in the string S. Write your answer to stdout.

## sample

aabbcc
1

a