Cho xâu \(S\) và vị trí \(i\). Tìm palindrome con dài nhất trong xâu \(S\) chứa ký tự tại vị trí \(i\).

Định dạng đầu vào

• Dòng 1: xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng 2: số nguyên \(i\) (\(0 \le i < |S|\)).

Định dạng đầu ra

• In ra độ dài palindrome con dài nhất chứa vị trí \(i\).

Ví dụ

Input:

abacaba
3

Output:

5

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).