트리 인코딩

이진 트리는 비어 있거나, 하나의 루트 노드와 왼쪽 서브트리 및 오른쪽 서브트리로 이루어진다. 이 문제에서 모든 노드에는 알파벳 소문자 하나가 적혀 있다. 어떤 이진 트리가 다음 두 조건을 만족할 때, 그리고 그럴 때에만 이진 검색 트리라고 한다.

1. 어떤 노드의 왼쪽 서브트리에 있는 모든 문자는 그 노드의 문자보다 사전순으로 앞선다.
2. 어떤 노드의 오른쪽 서브트리에 있는 모든 문자는 그 노드의 문자보다 사전순으로 뒤에 온다.

다음은 4개의 노드를 가진 이진 검색 트리의 예이다.

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

위와 같은 이진 검색 트리를 루트, 왼쪽 서브트리, 오른쪽 서브트리 순서로 전위 순회하면 cbad, cabd, acbd 같은 문자열을 얻을 수 있다.

N개의 노드를 가진 모든 이진 검색 트리를 생각하자. 노드에 적힌 문자는 a부터 알파벳 순서대로 N개이다. 각 트리를 전위 순회하여 얻은 문자열을 모두 모은 뒤 사전순으로 정렬한다.

N과 index가 주어질 때, 정렬된 목록에서 index번째 문자열을 출력하는 프로그램을 작성하라. index는 1부터 시작한다.

첫째 줄에 트리의 크기 N과 index가 주어진다. N은 19 이하의 자연수이고, index는 2,000,000,000 이하의 자연수이다. N = 19일 때 가능한 이진 검색 트리의 개수는 2,000,000,000보다 작다.

첫째 줄에 정답 문자열을 출력한다. 해당하는 트리가 없으면 -1을 출력한다.