K-th DuoPalindrome

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

Input	Output
cbaabccbabca 5	cabbaccabbac

Input	Output
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.