Cho xâu \(S\). Hàm Z \(Z[i]\) là độ dài lớn nhất của xâu con bắt đầu tại vị trí \(i\) mà trùng khớp với tiền tố của \(S\). Hãy tính mảng Z cho xâu \(S\).

Quy ước: \(Z[0] = 0\) (hoặc một số tài liệu đặt bằng \(|S|\), ta dùng \(Z[0] = 0\)).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)), chỉ gồm chữ cái in thường.

Định dạng đầu ra

• In ra \(N\) số nguyên \(Z[0], Z[1], \dots, Z[N-1]\), cách nhau bởi dấu cách.

Ví dụ

Input:

aabaaab

Output:

0 1 0 2 3 1 0

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).