Border của xâu là xâu con vừa là tiền tố vừa là hậu tố (và khác chính xâu). Hãy sử dụng mảng prefix function của KMP để tìm tất cả các border của xâu \(S\).

Định nghĩa mở rộng: Trong bài này, "border" bao gồm cả xâu rỗng (độ dài 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 độ dài các border theo thứ tự tăng dần, cách nhau bởi dấu cách. Luôn in border độ dài 0 (xâu rỗng).

Ví dụ

Input:

abacab

Output:

0 2

Ràng buộc

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