Problem C: FSA

Problem C: FSA

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1855  Solved: 734
[Submit][Status][Web Board]

Description

As learned in the lecture, FSA can be used to solve string matching problems. Here you are given a string \(S\), and you are required to output it's transition function according to the FSA algorithm.

Input

One line, indicating the input string \(S\) \((1\leq |S| \leq 10^5)\). The string contains only lowercase letters.

Output

\(|S|\) lines, each containing 26 integers, indicating the transition function.

Sample Input

aabaaabb

Sample Output

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
4 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

HINT

[Submit][Status]