Cho một xâu \(S\). Với mỗi vị trí \(1 \leq i \leq S.length\), hãy in ra độ dài tiền tố dài nhất của \(S\) khớp với hậu tố xuất phát tại \(i\) của nó. Nói cách khác, hãy in ra số \(j\) lớn nhất có thể mà \(S[1..j] = S[i..i + j - 1]\) hoặc in ra \(0\) nếu không tồn tại số \(j\) nào như vậy.

Input

• Gồm một dòng chứa một xâu \(S\) độ dài không quá \(300,000\).

Output

• In ra \(S.length\) số nguyên trên một dòng. Số thứ \(i\) là độ dài tiền tố tương ứng với hậu tố tại \(i\).

Example

aabaacd

7 1 0 2 1 0 0