Tree Encoding

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.

1. Every letter in a node's left subtree comes before the node's letter in lexicographic order.
2. 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.

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.

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