부분 염기서열

길이가 n인 염기서열 S가 주어진다. S는 문자 A, C, G, T로 이루어진 문자열이다.

이 문제에서 부분 염기서열은 S에서 연속한 한 구간을 잘라 만든 문자열을 뜻한다. 예를 들어 AGCT의 부분 염기서열에는 AG, GC, AGC, AGCT 등이 있다. AC는 A 바로 다음에 C가 나오지 않으므로 부분 염기서열이 아니다.

서로 다른 부분 염기서열 중 S 안에서 m번 이상 나타나는 것만 생각한다. 예를 들어 AGAG에서는 A, G, AG가 각각 두 번 이상 나타난다.

조건을 만족하는 부분 염기서열의 전체 개수와, 정렬했을 때 K번째 부분 염기서열을 구하라. 정렬 기준은 길이가 짧은 문자열이 먼저 오고, 길이가 같으면 사전순으로 작은 문자열이 먼저 온다.

첫째 줄에 세 정수 n, m, K가 주어진다.

둘째 줄에 길이가 n인 염기서열 S가 주어진다.

K는 조건을 만족하는 부분 염기서열의 개수를 넘지 않는다.

첫째 줄에 m번 이상 나타나는 서로 다른 부분 염기서열의 개수를 출력한다.

둘째 줄에 정렬 순서에서 K번째인 부분 염기서열을 출력한다.

참고로 제공된 입력에서 m=4일 때 조건을 만족하는 부분 염기서열은 A, C, G, T, GG, AT, AG, GA, TC, CG, ATC, TCG, ATCG이다. 이 목록은 정렬 순서가 아니다.