Trong buổi ôn luyện môn Tiếng Anh, bạn Bình phát hiện trong bài tập Cô giao có một số từ mà khi viết từ phải sang trái hay từ trái sang phải thì từ đó không thay đổi. VD: madam, ioi,… Và Bình hiểu một từ như là xâu con (Xâu con là một dãy các kí tự liên tiếp nhau được trích ra từ xâu ban đầu). Thích thú với sự phát hiện này, về nhà Bình lên Google tra cứu thì biết được các từ đó được gọi là xâu palindrome (xâu đối xứng).

Anh của Bình cũng là một giáo viên. Anh ta muốn hỗ trợ em mình ôn tập nên cho thêm bài tập, nhưng lại yêu cầu em mình phải xác định được xâu thứ \(i\) trong các xâu palindrome có độ dài \(k\). Nếu đưa ra đúng kết quả thì Bình sẽ được thưởng một chuyến du lịch sau khi thi xong.

Yêu cầu: Cho một xâu \(st\) độ dài không quá \(10^{5}\) kí tự, các kí tự được lấy từ tập ‘a’.. ‘z’; hãy đưa ra xâu con palindrome thứ \(i\) của \(st\) có độ dài bằng \(k\) (thứ tự \(i\) được tính tăng dần từ trái qua phải).

Dữ liệu vào:

• Dòng 1 chứa xâu \(st\) có độ dài không quá \(10^{5}\) kí tự.

• Dòng 2 chứa 2 số nguyên dương \(k\) và \(i\) (\(0 < k \leq\) độ dài xâu \(st\); \(1 \leq i \leq 10^{6}\)), giữa hai số cách nhau một dấu cách.

Kết quả:

+ Ghi duy nhất xâu con palindrome thứ \(i\) của \(st\) có độ dài bằng \(k\). Nếu không tồn tại xâu con palindrome thứ \(i\) của \(st\) có độ dài bằng \(k\) thì in ra ***.

Ví dụ:

Ràng buộc:

• Độ dài xâu st không quá \(10^{5}\) kí tự.

• \(0 < k \leq\) độ dài xâu \(st\); \(1 \leq i \leq 10^{6}\).