Nth Most Frequent Character

Given a string s and an integer n, your task is to determine the n-th most frequent character in the string. The frequency ranking is done in descending order, and if two characters have the same frequency, the lexicographical order (i.e., alphabetical order) is used as a tiebreaker. In other words, for any two characters with equal frequency, the one with a smaller value in lexicographical order is considered more frequent.

Formally, let \( f(c) \) denote the frequency of character \( c \) in the string. After sorting the characters so that for any two characters \( c_1 \) and \( c_2 \) either \( f(c_1) > f(c_2) \) or \( f(c_1) = f(c_2) \) and \( c_1 < c_2 \) (in lexicographical order), the n-th element in this ordering is the answer.

For example:

• For s = "aaabbc" and n = 2, the answer is 'b'.
• For s = "a" and n = 1, the answer is 'a'.
• For s = "abcdef" and n = 3, the answer is 'c'.

inputFormat

The input is given on two lines:

1. The first line contains the string s.
2. The second line contains the integer n, which denotes the rank of the frequency.

outputFormat

Output the n-th most frequent character in the string.

aaabbc
2

b