Problem B: [Easy] Find Next

Problem B: [Easy] Find Next

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 1149  Solved: 522
[Submit][Status][Web Board]

Description

KMP algorithm is an improved string matching algorithm proposed by D.E.Knuth, J.H.Morris and V.R.Pratt, so it is called Knut Morris Pratt operation (KMP algorithm for short). The core of KMP algorithm is to use the information after matching failure to reduce the matching times between pattern string and main string to achieve the purpose of fast matching. The specific implementation is realized by a next() function, which contains the local matching information of pattern string.

Now give you a text S, please output its next array.

Input

a line contains a text string S. |S| <= 1000000

Output

Output s.length lines. The i line indicates next[i] for S.

Sample Input

ababc

Sample Output

0
0
1
2
0

HINT

[Submit][Status]