Một ứng dụng thú vị của máy tính là phân tích dữ liệu sinh học, chẳng hạn các chuỗi DNA. Về mặt sinh học, một sợi DNA là chuỗi các nucleotide Adenine, Cytosine, Guanine và Thymine, lần lượt được biểu diễn bằng các ký tự A, C, G và T. Vì vậy, một sợi DNA có thể được biểu diễn bằng một xâu gồm bốn ký tự này, gọi là một chuỗi DNA.

Đôi khi các nhà sinh học không thể xác định một số nucleotide. Khi đó, ký tự N được dùng để biểu diễn một nucleotide chưa biết: nó có thể là bất kỳ một ký tự nào trong A, C, G, T. Một chuỗi có ít nhất một ký tự N được gọi là chuỗi chưa hoàn chỉnh; ngược lại, đó là chuỗi hoàn chỉnh. Một chuỗi hoàn chỉnh được gọi là phù hợp với chuỗi chưa hoàn chỉnh nếu có thể thu được nó bằng cách thay mỗi ký tự N bằng một trong bốn nucleotide. Chẳng hạn, ACCCT phù hợp với ACNNT, còn AGGAT thì không.

Các nucleotide được sắp thứ tự như trong bảng chữ cái tiếng Anh:

Một chuỗi DNA thuộc dạng 1 nếu mỗi nucleotide trong chuỗi bằng hoặc đứng trước nucleotide ngay bên phải nó theo thứ tự trên. Ví dụ, AACCGT thuộc dạng 1, còn AACGTC thì không.

Với \(j>1\), một chuỗi thuộc dạng \(j\) nếu nó thuộc dạng \(j-1\), hoặc là phép nối một chuỗi dạng \(j-1\) với một chuỗi dạng 1. Ví dụ, AACCC, ACACC và ACACA đều thuộc dạng 3, còn GCACAC và ACACACA thì không.

Các chuỗi DNA được sắp theo thứ tự từ điển, như cách sắp các từ trong từ điển. Chẳng hạn, chuỗi dạng 3 đầu tiên có độ dài \(5\) là AAAAA, và chuỗi cuối cùng là TTTTT. Với chuỗi chưa hoàn chỉnh ACANNCNNG, bảy chuỗi dạng 3 đầu tiên phù hợp với nó, theo thứ tự, là ACAAACAAG, ACAAACACG, ACAAACAGG, ACAAACCAG, ACAAACCCG, ACAAACCGG và ACAAACCTG.

Hãy tìm chuỗi dạng \(K\) đứng thứ \(R\) theo thứ tự từ điển trong số các chuỗi hoàn chỉnh phù hợp với chuỗi chưa hoàn chỉnh cho trước có độ dài \(M\). Thứ tự được đánh số bắt đầu từ \(1\).

Dữ liệu vào

Dòng đầu chứa ba số nguyên \(M,K,R\).

Dòng thứ hai chứa xâu độ dài \(M\) biểu diễn chuỗi chưa hoàn chỉnh, gồm các ký tự A, C, G, T, N.

Bảo đảm tổng số chuỗi dạng \(K\) phù hợp với chuỗi đã cho không vượt quá \(4\cdot 10^{18}\), và \(R\) không vượt quá tổng số này.

Dữ liệu ra

In trên một dòng chuỗi dạng \(K\) đứng thứ \(R\) phù hợp với chuỗi đã cho.

Ràng buộc

Các giá trị lớn trong bài cần được lưu bằng kiểu số nguyên 64 bit: long long trong C/C++ hoặc Int64 trong Pascal. Trong C/C++, có thể đọc và ghi long long bằng scanf("%lld", &a) và printf("%lld\n", a); Pascal không cần cách đọc, ghi đặc biệt cho Int64.

Giới hạn thời gian: \(1\) giây. Giới hạn bộ nhớ: \(128\) MB. Một bộ dữ liệu chỉ được tính điểm khi kết quả hoàn toàn đúng.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

9 3 5
ACANNCNNG

ACAAACCCG

5 4 10
ACANN

ACAGC

Nguồn

Olympic Tin học châu Á – Thái Bình Dương 2008, bài DNA.