이진 탐색 트리 코드

이진 트리는 비어 있거나, 하나의 정점과 그 정점에 연결된 두 개의 트리로 이루어집니다. 이 두 트리를 각각 왼쪽 서브트리와 오른쪽 서브트리라고 부릅니다. 각 정점에는 영어 알파벳 소문자가 하나씩 들어 있습니다. 다른 어떤 정점의 서브트리도 아닌 정점을 루트라고 합니다.

모든 정점에서 다음 조건이 성립하면 그 트리를 이진 탐색 트리(BST)라고 합니다. 왼쪽 서브트리에 있는 모든 글자는 알파벳 순서상 루트의 글자보다 앞서고, 오른쪽 서브트리에 있는 모든 글자는 루트의 글자보다 뒤에 옵니다.

BST의 코드는 다음과 같이 정의합니다.

• 트리가 비어 있으면 빈 문자열(글자 0개)입니다.
• 그렇지 않으면 루트의 글자로 시작하여, 왼쪽 서브트리의 코드, 오른쪽 서브트리의 코드를 차례로 이어 붙인 문자열입니다.

영어 알파벳의 처음 $k$개 글자를 정점에 담은, 정점이 $k$개인 BST를 모두 생각합니다. 이들의 코드를 사전순으로 나열한 목록에서 $n$번째 코드를 $(n, k)$-코드라고 합니다.

예를 들어 정점이 4개인 BST는 정확히 14개 있으며, 그 코드를 사전순으로 나열하면 다음과 같습니다.

abcd abdc acbd adbc adcb bacd badc cabd cbad dabc dacb dbac dcab dcba

문자열 badc는 $(7, 4)$-코드이며, 아래 그림의 BST에 대응합니다.

다음을 수행하는 프로그램을 작성하세요.

• 표준 입력에서 두 정수 $n$과 $k$를 읽고,
• $(n, k)$-코드를 구하여,
• 표준 출력에 씁니다.

표준 입력의 첫 번째 줄이자 유일한 줄에 두 양의 정수 $n$과 $k$가 공백 하나로 구분되어 주어집니다. $1 \le k \le 19$입니다. $n$은 정점이 $k$개인 BST 코드의 총 개수보다 크지 않습니다.

표준 출력의 첫 번째 줄이자 유일한 줄에 $(n, k)$-코드에 해당하는 소문자 단어 하나를 출력합니다.