Xâu Palindrome

Xâu palindrome hay còn gọi là xâu gương, gọi vậy bởi vì khi viết ngược lại xâu thì nó vẫn là chính nó.

Xâu con là xâu nhận được khi xóa một vài kí tự nào đó trong xâu gốc.

Cho trước một xâu chỉ gồm kí tự latin in thường. Kiểm tra xem xâu đó có chứa một xâu con đối xứng có độ dài \(k\) hay không. Nếu có, in ra xâu đó, nếu không có, in ra xâu con đối xứng có độ dài lớn nhất.

Nếu có nhiều xâu thỏa mãn, bạn chỉ cần in đáp án bất kì.

Input

Gồm một xâu kí tự latin in thường có độ dài \(n\) \((n <= 5.10^4)\).

Dòng thứ hai là số nguyên \(k\) \((k <= 100)\).

Output

Xâu thỏa mãn đề bài.

Example

bbbabcbbb
7

bbbbbbb

Scoring

\(30\%\) số test \(n <= 20\).

\(20\%\) số test \(n <= 100\).

\(20\%\) số test \(n <= 1000\).

\(30\%\) số test còn lại \(n <= 5.10^4\).