Cho xâu \(S\), hãy đếm số xâu con phân biệt của \(S\) (xâu con phân biệt nghĩa là chuỗi ký tự khác nhau, không phải vị trí khác nhau). Sử dụng mảng hậu tố và LCP.

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

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).

Định dạng đầu ra

• In ra số nguyên duy nhất là số xâu con phân biệt.

Ví dụ

Input:

ababa

Output:

9

Giải thích: Các xâu con phân biệt: a, b, ab, ba, aba, bab, abab, baba, ababa.

Ràng buộc

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