Cho một xâu \(S\). Xây dựng mảng hậu tố (Suffix Array) và mảng LCP[i] (Longest Common Prefix) giữa hậu tố thứ i và hậu tố thứ i+1 trong mảng hậu tố. Sau đó, cho hai chỉ số i, j trong mảng hậu tố, hãy in ra độ dài tiền tố chung dài nhất của hai hậu tố này.

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

• Dòng đầu chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).
• Dòng thứ hai chứa hai số nguyên \(i, j\).

Định dạng đầu ra

• In ra độ dài tiền tố chung dài nhất của hai hậu tố tương ứng.

Ví dụ

Input:

banana
1 2

Output:

3

Ràng buộc

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