Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

K-th DuoPalindrome

Limits: 1s, 512 MB

Alice likes playing with Palindromes (strings that read the same backward as forward, such as ‘madam’ or ‘racecar’). Today, she’s playing with a special kind of Palindrome which she calls DuoPalindrome. A DuoPalindrome is a Palindrome which has even length, and when this string is cut in half, the resulting two strings are also Palindrome. For example, let’s consider the string ‘xyyxxyyx’. This string is a DuoPalindrome because it’s a Palindrome, its length is 8 which is an even number, and if we cut this string in half, we get ‘xyyx’ and ‘xyyx’, which are also Palindromes.

Today, Alice has made a DuoPalindrome and then she left the room to do her homework. While she was away, Bob came and re-arranged some letters (possibly none) of the DuoPalindrome. Note that, he didn’t change or destroy any of letters, he just re-arranged them. When Alice came back, she was very upset to see this and now she wants to retrieve her original string. She doesn’t remember exactly what her string was, but she does remember that her DuoPalindrome was lexicographically the K-th smallest DuoPalindrome among all the DuoPalindromes that can be made by re-arranging the letters of this string. Can you help her retrieve her string?

Input

The first and only line of the input contains a string s, representing the string after Bob’s re-arrangement and an integer K (1 ≤ K ≤ 1016). The string s consists of lowercase english letter only, where each letter will appear at most 4 times. It’s guaranteed that the length of s is even and by re-arranging the letters of s, it’s possible to make a DuoPalindrome. Let, N = number of different DuoPalindromes you can make by re-arranging the letters of s. It’s guaranteed that K ≤ N.

Output

In a single line, print the lexicographically K-th smallest DuoPalindrome that can made by re-arranging the letters of s.

Samples

InputOutput
cbaabccbabca 5
cabbaccabbac
InputOutput
yxyzzxzyyz 2
zyxyzzyxyz

Explanation of Sample Case 1: It’s possible to make 6 different DuoPalindromes by re-arranging the letters of s and they are: ‘abccbaabccba’, ‘acbbcaacbbca’, ‘baccabbaccab’, ‘bcaacbbcaacb’, ‘cabbaccabbac’, ‘cbaabccbaabc’

Among them, ‘cabbaccabbac’ is lexicographically 5-th smallest, so that’s our answer.

Author
  • Sherlock221b's Avatar

    Sherlock221b

    Imran is a part-time philosopher who enjoys solving programming problems, climbing mountains and sports.
Discussion
Submit

Login to submit