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.

Well, you also had the solution in your last blog. Therefore, this blog makes no sense.

No it wasn't the correct one , here the length is

`|x| <= 1000`

so`3^1000`

will not workWhat is the problem with 3

^{1000}?-_-

You can review your input string as a decimal number. So, answer will be your string as number + input number. Base is 3, not 10.

Can't understand your idea, could you explain more?

He meant that you can represent string

aabcas number in base 3:aabc~ (0012)_{3}After that your problem is just some arithmetics in base 3

It's some sort of natural numeric system yes, but not quite. imagine you are writing numbers in base 3, but your digits aren't 0, 1, 2 but 1, 2, 3 (you can represent all positive integers this way, uniquely). Lets call this base _3. If you can transform any number from base 10 to base _3 (it's easy in this case with

n≤ 10^{9}), and you can add up two numbers in base _3 (ad-hoc code, a simple for cycle with rules :) ) then you can solve your problem...I understand your idea, but suppose we have something like this:

aa 5

What is the number that represents the combination (aa) in base _3 and what is the representation of 5 in the base _3?

aa in base _3 is 1 * 3

^{1}+ 1 * 3^{0}= 45 = 1 * 3

^{1}+ 2 * 3^{0}, so it is abThe tricky example is 6:

6 = 2 * 3

^{1}+ 0 * 3^{0}, but we cant represent that (cos we have no zero digit, that's why I said is not quite a numeric system), instead we use 6 = 1 * 3^{1}+ 3 * 3^{0}(that is ac).The answer to the problem as follow (this solution works even for

`|x| <= 10^6 and n <= 10^18`

):if

`|x| < 1001`

then add`(char('a' - 1))`

to the beginning of`x`

until we get`|x| == 1001`

.`char ('a' - 1)`

means the character that is before the letter`'a'`

.Now we will use simple math:

Suppose the index of the last letter of

`x`

is`j ( j = 1000 )`

;Moving

`x[j]`

forward by one will cost`(1)`

.Moving

`x[j-1]`

forward by one will cost`(3)`

.so moving any letter

`x[i]`

forward one step will cost`3^(j-i)`

.So the problem now is easy:

The reason behind

`(1000-i) <= 20`

because`(10^9 <= 3^20)`

Simple modification on the code above you can solve the problem for

`(|x| <= 10^6)`

Please notify me if you see something wrong or I've missed something .