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\).