Trong thuật toán KMP, hàm tiền tố (prefix function) \($\pi[i]$\) được định nghĩa là độ dài lớn nhất của tiền tố thực sự của xâu \($S[0 \ldots i]$\) đồng thời là hậu tố của nó. Hãy viết chương trình tính hàm tiền tố cho xâu \(S\).

Đị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 \(N\) số nguyên \($\pi[0], \pi[1], \dots, \pi[N-1]$\) trên một dòng.

Ví dụ

Input:

aabaaab

Output:

0 1 0 1 2 2 3

Giải thích: Với S = "aabaaab":

• \(\pi[0] = 0\) (xâu a không có tiền tố thực sự)
• \(\pi[1] = 1\) (aa có tiền tố-hậu tố a)
• \(\pi[2] = 0\) (aab không có)
• \(\pi[3] = 1\) (aaba có a)
• \(\pi[4] = 2\) (aabaa có aa)
• \(\pi[5] = 2\) (aabaaa có aa)
• \(\pi[6] = 3\) (aabaaab có aab)

Ràng buộc

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