Giải bài trực tuyến

Hôm nay chúng ta sẽ sẽ cùng ôn về Suffix Array !!!

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 a 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'

Chú thích:

• Với S[i..j] (i
• S[k] là kí tự thứ k của xâu S.
• |S| là độ dài của xâu S hay số lượng kí tự trong xâu S.
• Nếu k > |S| thì S[k] là một kí tự rỗng, kí tự rỗng được xem là nhỏ hơn bất kì kí tự nào khác

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.
• 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

Giới hạn

• 20% test đầu tiên có N <= 20; K = 1;
• 10% test tiếp theo có N <= 20; K <= 1000;
• 10% test tiếp theo có N <= 20; K <= 10¹²;
• 20% test tiếp theo có N <= 1000; K = 1;
• 20% test tiếp theo có N <= 1000; K <=1000;
• 20% test cuối cùng có N <= 1000; K <= 10¹²;

Example

Input:
4 2
3 4 1 2

Output:
bdab

Giải thích:
3 xâu đầu tiên theo thứ tự từ điển có Suffix Array như đã cho là:
bcab
bdab
beab
K = 2 nên kết quả sẽ là xâu 'bdab'