The Kth Anagram in Alphabetical Order

An anagram of a string is any string you can form with exactly the same letters as the original. The original string counts as one of its own anagrams.

For example, ACM has 6 anagrams, in alphabetical order: ACM, AMC, CAM, CMA, MAC, MCA. The string ICPC has 12 anagrams, in alphabetical order: CCIP, CCPI, CICP, CIPC, CPCI, CPIC, ICCP, ICPC, IPCC, PCCI, PCIC, PICC.

Given a string and a rank $K$, find the $K$th anagram of that string in alphabetical order.

Each line holds one query: the original word, a space, then the rank $K$. A word uses uppercase letters A to Z only and has length at most 16. $K$ is at least 1 and at most the number of distinct anagrams of the word. The line # 0 ends the input. That line is not a query.

In the largest cases $K$ reaches $16! = 20922789888000$, so store it in a 64-bit integer. Use long in Java or long long in C++.

For each query, print the $K$th anagram of the word on its own line.