Cho một xâu, hãy tính với mỗi vị trí độ dài của palindrome dài nhất kết thúc tại vị trí đó.

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~. Mỗi ký tự nằm trong khoảng a–z.

Kết quả

In ra ~n~ số: độ dài của mỗi palindrome.

Giới hạn

• ~1 \le n \le 2 \cdot 10^5~

Ví dụ

Dữ liệu vào:

ababbababaa

Kết quả:

1 1 3 3 2 4 6 8 5 5 2