Cho xâu \(S\), hãy tìm xâu palindrome con dài nhất trong \(S\). Sử dụng thuật toán Manacher để đạt độ phức tạp \(O(N)\).

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

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)), chỉ gồm chữ cái in thường.

Định dạng đầu ra

• In ra độ dài palindrome con dài nhất.

Ví dụ

Input:

abacaba

Output:

7

Giải thích: Cả xâu abacaba là palindrome.

Ràng buộc

• 50% số điểm: \(|S| \le 1000\).
• 50% số điểm còn lại: \(|S| \le 10^5\).