Tree Encoding

Time limit2sMemory limit128 MB

Summary

Given N and an index, find the k-th lexicographically smallest preorder traversal string among all binary search trees built from the first N letters, using Catalan number counting.

Level: Medium6 of 10
Topics: Combinatorics, Math, Recursion, Tree
Solved: No attempts yet

Problem

A binary tree is either empty, or consists of one root node, a left subtree, and a right subtree. In this problem, every node stores one lowercase English letter. A binary tree is a binary search tree if and only if it satisfies both conditions below.

Every letter in a node's left subtree comes before the node's letter in lexicographic order.
Every letter in a node's right subtree comes after the node's letter in lexicographic order.

Here are examples of binary search trees with 4 nodes.

    c         c      a
   / \       / \      \
  b   d     a   d      c
 /           \        / \
a             b      b   d

If such binary search trees are traversed in preorder, visiting the root first, then the left subtree, then the right subtree, strings such as cbad, cabd, and acbd can be obtained.

Consider all binary search trees with N nodes. The node labels are the first N lowercase letters starting from a. For every tree, take its preorder traversal string, collect all such strings, and sort them lexicographically.

Given N and index, write a program that prints the index-th string in this sorted list. index is 1-based.

Input

The first line contains the tree size N and index. N is a positive integer at most 19, and index is a positive integer at most 2,000,000,000. When N = 19, the number of possible binary search trees is less than 2,000,000,000.

Output

Print the answer string on the first line. If no such tree exists, print -1.

Examples5

Example 1
Input
```
4 9
```
Expected output
```
cbad
```
Example 2
Input
```
2 1
```
Expected output
```
ab
```
Example 3
Input
```
2 2
```
Expected output
```
ba
```
Example 4
Input
```
2 3
```
Expected output
```
-1
```
Example 5
Input
```
15 14023
```
Expected output
```
abcdeohgfniljkm
```