Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Một xâu ký tự được gọi là xâu đối xứng nếu đọc xâu đó từ trái qua phải cũng như đọc nó từ phải qua trái ta thu được cùng một xâu. Một xâu ký tự được gọi là xâu đối xứng cấp 0 nếu tồn tại một cách sắp xếp lại các ký tự của nó để thu được một xâu đối xứng.  Một xâu s=s₁s₂…s_n gồm n ký tự (ta gọi n là độ dài của xâu s) được gọi là xâu đối xứng cấp k nếu nó thỏa mãn các điều kiện sau:

1)       s là xâu đối xứng cấp 0;

2)       tồn tại k vị trí 1 < i₁ < i₂ < …< i_k  < n, sao cho xâu con gồm i_j  ký tự đầu tiên của xâu s là xâu đối xứng cấp 0, j = 1, 2,…, k.

Dễ thấy, nếu một xâu là xâu đối xứng cấp k thì nó cũng là xâu đối xứng cấp m với 0 ≤ m < k.

Ví dụ, các xâu ‘ada’, ‘abba’ là các xâu đối xứng; xâu ‘daa’ là xâu đối xứng cấp 0; xâu ‘abab’  là xâu đối xứng cấp 1 (vị trí thỏa mãn định nghĩa là i₁ = 3); xâu ‘ababd’ là xâu đối xứng cấp 2 (2 vị trí thỏa mãn định nghĩa là i₁ = 3 và i₂ = 4).

Ký hiệu S(n, k, Ω) là dãy tất cả các xâu đối xứng cấp k độ dài n chỉ gồm các ký tự thuộc tập ký tự Ω được liệt kê theo thứ tự từ điển, đánh số bắt đầu từ 1.

Ví dụ, với n=3; k=1; Ω={‘v’, ‘n’}, dãy S(3, 1, {‘v’, ‘n’}) gồm 4 xâu được liệt kê theo thứ tự từ điển và đánh số thứ tự bắt đầu từ 1 sau đây:

1. ‘nnn’                                           

2. ‘nnv’                                           

3. ‘vvn’                                   

4. ‘vvv’

Yêu cầu: Cho n, k, Ω và số nguyên t, hãy đưa ra xâu thứ t trong dãy S(n, k, Ω).

Input

Dòng đầu chứa hai số nguyên không âm n, k (k ≤ n−2; 2 ≤ n ≤ 50);

• Dòng thứ hai chứa các ký tự của tập Ω được ghi nhận bởi một xâu gồm không quá 5 chữ cái in thường lấy từ tập 26 chữ cái tiếng Anh từ ‘a’ đến ‘z’;
• Dòng thứ ba chứa số nguyên dương t (t không lớn hơn số lượng phần tử của S(n, k, Ω)).

Các số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra xâu thứ t của dãy S(n, k, Ω).

Example

Input:
3 1
vn
2

Output:
nnv