DNA 서열

컴퓨터로 해결하는 흥미로운 문제 중 하나는 DNA 서열과 같은 생물학적 자료를 분석하는 것이다. 하나의 DNA 가닥은 뉴클레오타이드인 아데닌, 사이토신, 구아닌, 타이민이 이어진 사슬이며, 이 네 뉴클레오타이드는 각각 A, C, G, T로 나타낸다. 따라서 DNA 가닥은 이 네 문자로 이루어진 문자열로 표현할 수 있고, 이 문자열을 DNA 서열이라고 한다.

DNA 가닥의 어떤 위치에 있는 뉴클레오타이드가 무엇인지 정확히 알 수 없는 경우가 있다. 이때 그 위치의 미확인 뉴클레오타이드를 문자 N으로 표시한다. 즉 N은 A, C, G, T 중 무엇이든 될 수 있는 와일드카드 문자이다. N을 하나 이상 포함하는 서열을 불완전 서열, N이 하나도 없는 서열을 완전 서열이라고 한다. 불완전 서열의 각 N을 네 뉴클레오타이드 중 하나로 바꾸어 어떤 완전 서열을 만들 수 있으면, 그 완전 서열은 주어진 불완전 서열과 일치한다고 말한다. 예를 들어 ACCCT는 ACNNT와 일치하지만, AGGAT는 일치하지 않는다.

네 뉴클레오타이드에는 알파벳 순서에 따라 A < C < G < T의 순서를 준다. 어떤 서열에서 모든 뉴클레오타이드가 자신의 바로 오른쪽 뉴클레오타이드와 같거나 그보다 앞선 순서이면(즉 왼쪽에서 오른쪽으로 감소하지 않으면) 그 서열을 형태-1로 분류한다. 예를 들어 AACCGT는 형태-1이지만 AACGTC는 형태-1이 아니다.

일반적으로 형태-$j$ 서열은 다음과 같이 정의한다. 어떤 서열이 형태-$(j-1)$이거나, 또는 어떤 형태-$(j-1)$ 서열 하나와 어떤 형태-1 서열 하나를 이어 붙인 것이면 그 서열을 형태-$j$라고 한다. 예를 들어 AACCC, ACACC, ACACA는 형태-3이지만, GCACAC와 ACACACA는 형태-3이 아니다.

서열들 사이의 순서는 사전에서 단어를 나열하는 방식과 같은 사전식 순서로 정한다. 따라서 길이가 5인 형태-3 서열 중 첫 번째는 AAAAA이고 마지막은 TTTTT이다. 다른 예로, 불완전 서열 ACANNCNNG와 일치하는 형태-3 서열을 사전식 순서로 처음 7개 나열하면 다음과 같다.

ACAAACAAG, ACAAACACG, ACAAACAGG, ACAAACCAG, ACAAACCCG, ACAAACCGG, ACAAACCTG

길이가 $M$인 불완전 서열이 주어질 때, 그 서열과 일치하는 형태-$K$ 서열들 중 사전식 순서로 $R$번째인 것을 찾는 프로그램을 작성하시오.

첫 번째 줄에 정수 세 개 $M$, $K$, $R$이 공백 하나로 구분되어 주어진다. ($1 \le M \le 50000$, $1 \le K \le 10$, $1 \le R \le 2 \times 10^{12}$)

두 번째 줄에 길이가 $M$인 불완전 서열이 주어진다. 이 문자열은 A, C, G, T, N으로만 이루어져 있다.

주어진 불완전 서열과 일치하는 형태-$K$ 서열의 개수는 $4 \times 10^{18}$ 이하이므로 부호 있는 64비트 정수(예: C/C++의 long long)로 나타낼 수 있으며, $R$은 이 개수보다 작거나 같다.

주어진 불완전 서열과 일치하는 형태-$K$ 서열들 중 사전식 순서로 $R$번째인 서열을 첫 번째 줄에 출력한다.