Incremental Double Free Strings

Time limit2sMemory limit512 MB

Summary

Find the nth string of length k(k+1)/2 that uses one letter j times for each j up to k and has no two equal adjacent letters, in alphabetical order.

Level: Hard9 of 10
Topics: Combinatorics, Dynamic programming, Greedy, String matching
Solved: No attempts yet

Problem

A string is double free if no two adjacent letters are the same.

A string is k-incremental if, for every j from 1 to k, exactly one character occurs j times, and the length of the string is $1+2+3+\cdots+(k-1)+k$ . For example, when k = 3, a 3-incremental string has one character that appears once, another that appears twice, and another that appears three times, in any order, for a total length of 6.

A string that meets both conditions is k-incremental and double free. Fix a k and list every such string of lowercase letters in alphabetical order. Here are two examples of that list.

k = 2: aba, aca, ada, ..., aya, aza, bab, bcb, bdb, ..., zxz, zyz

k = 3: ababac, ababad, ..., ababay, ababaz, ababca, ..., zyzyzx

What is the nth string in the alphabetized list of all k-incremental, double free strings?

Input

The input is a single test case. Your program may be run several times on different inputs. The input has exactly one line with two integers k and n ( $1 \le k \le 26$ , $1 \le n \le 10^{18}$ ), asking for the nth string in the alphabetically sorted list of all k-incremental, double free strings.

Output

Print the nth k-incremental, double free string in the alphabetized list. If no such string exists, print -1.

Examples3

Example 1
Input
```
2 650
```
Expected output
```
zyz
```
Example 2
Input
```
2 651
```
Expected output
```
-1
```
Example 3
Input
```
5 12345678901234
```
Expected output
```
yuzczuyuyuzuyci
```