{"code":"cwdsstr","name":"String Reconstruction","description":"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}$.\r\n\r\nSau đó 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$.\r\n\r\nCuố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$.\r\n\r\nVí dụ:\r\n - Cho xâu $S=$`bcab`.\r\n - Ta có $4$ xâu con:\r\n     - $T_1=$`bcab`\r\n     - $T_2=$`cab`\r\n     - $T_3=$`ab`\r\n     - $T_4=$`b`\r\n - 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$.\r\n - Vậy ta có suffix array là $3$, $4$, $1$, $2$.\r\n\r\n**Yêu cầu:**\r\n - 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$.\r\n - Để đơn giản các xâu chỉ bao gồm các kí tự từ `a` đến `z`.\r\n\r\n\r\n#### Input:\r\n - 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)$.\r\n - Dòng thứ $2$ chứa $N$ số nguyên phân biệt là dãy $a_1$, $a_2$,..., $a_N$.\r\n\r\n#### Output: \r\n- 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$.\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 2\r\n        3 4 1 2\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        bdab\r\n        ```\r\n    ???+ warning \"Note\"\r\n        3 xâu đầu tiên theo thứ tự từ điển có Suffix Array như đã cho là:\r\n        - `bcab`\r\n        - `bdab`\r\n        - `beab`\r\n        \r\n        $K=2$ nên kết quả sẽ là xâu `bdab`.\r\n        \r\n**Nguồn bài**: VOS Round 23 - Lê Ðôn Khuê","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}