Cho \(1\) xâu \(S\) gồm \(n\) ký tự, ta sinh ra \(n\) xâu con của \(S\) là: \(T_1=S_{1..n}\), \(T_2=S_{2..n}\), \(T_3=S_{3..n}\),..., \(T_n=S_{n..n}\).

Sau đó ta sẽ sắp xếp \(n\) xâu \(T\) lại theo thứ tự từ điển tăng dần, \(1\) xâu \(A\) được xem là có thứ tự từ điển nhỏ hơn \(B\) nếu tồn tại \(1\) vị trí \(k\) sao cho \(A_{1..k-1}=B_{1..k-1}\) và \(A_k < B_k\).

Cuối cùng ta sẽ xây dựng mảng \(a_1\), \(a_2\),..., \(a_n\) với \(a_i=x\) nếu xâu \(T_x\) nằm ở vị trí \(i\) sau khi đã được sắp xếp tăng dần. Mảng \(a\) được gọi là Suffix Array của xâu \(S\).

Ví dụ:

• Cho xâu \(S=\)bcab.
• Ta có \(4\) xâu con:
  • \(T_1=\)bcab
  • \(T_2=\)cab
  • \(T_3=\)ab
  • \(T_4=\)b
• Mảng \(T\) sau khi sắp xếp lại theo thứ tự tăng dần là: \(T_3\), \(T_4\), \(T_1\), \(T_2\).
• Vậy ta có suffix array là \(3\), \(4\), \(1\), \(2\).

Yêu cầu:

• Cho trước Suffix Array \(a\) và số \(K\). Trong những xâu có Suffix Array \(a\), hãy tìm xâu \(S\) có thứ tự từ điển nhỏ thứ \(K\).
• Để đơn giản các xâu chỉ bao gồm các kí tự từ a đến z.

Input:

• Dòng đầu tiên có \(2\) số: \(N\), \(K\) lần lượt là số kí tự và thứ tự từ điển của xâu cần in ra \(\left(N\le 1000, K\le 10^{12}\right)\).
• Dòng thứ \(2\) chứa \(N\) số nguyên phân biệt là dãy \(a_1\), \(a_2\),..., \(a_N\).

Output:

• Gồm xâu kết quả in trên \(1\) dòng duy nhất, chỉ gồm các chữ cái thường từ a đến z, trường hợp không có kết quả thì in ra \(-1\).

4 2
3 4 1 2

bdab

Nguồn bài: VOS Round 23 - Lê Ðôn Khuê