Cho xâu \(S\) và hai chỉ số \(i, j\). Hãy in ra độ dài palindrome chung dài nhất giữa xâu con \(S[i..|S|-1]\) và \(S[j..|S|-1]\), tức là palindrome dài nhất xuất hiện ở cả hai vị trí bắt đầu này.

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

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng thứ hai chứa hai số \(i, j\) (\(0 \le i, j < |S|\)).

Định dạng đầu ra

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

Ví dụ

Input:

abacaba
0 4

Output:

3

Ràng buộc

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