Given the letters a, b and c , you're only allowed to use these letters.

First combinations that can be made from these letters are: (a) , (b) , (c) , (aa) , (ab) , (ac) , (ba) ....

What is the nth combination that is after the combination x ?

If two combinations have different length, the combination with smallest length comes first, and if they have the same length ** the smallest in alphabetical order comes first**.

Input:

x and n where (|x| <= 1000) and (n <= 10^9)

Examples:

a 2: means given the combination (a) what is the combination that is (2) steps after the combination (a)? Answer is (c)

aa 3: means given the combination (aa) what is the combination that is (3) steps after the combination (aa)? Answer is (ba)

Input:

a 2
b 3
c 1

Output:

c
ab
aa

I had posted this blog before, but I deleted it accidentally, sorry for this.