AZY的消失

题目描述

德塔斯图拉克市(Data Struc City)是一座神奇的城邦，市议会中深受人民群众爱戴的AZY大祭司突然消失，全无音讯。于是他的同事兼挚友，市议会秘书长Kevin组织了调查兵团，出城寻找AZY。

行军至一处峡谷，突然发现前方的路被一块遮天巨岩挡住，岩上有很多行文字，似乎只有根据文字解出密码才能顺利通过。Kevin并不知道如何解码，但他想起几天前，AZY还没有消失时，听他的这位老友谈起过一个古老的魔法，名叫KMP，其中的咒语记录在名叫NEXT的一串数字中，Kevin想，也许这咒语就可以解开巨石上的谜题。

输入

输入多组数据。 每组数据只有一行，为一个字符串(字符串长度为k,保证1<=k<=500)。

输出

对于每组数据，输出字符串的next数组。

输入样例

abcabc

输出样例

-1 0 0 0 1 2