Дима дописывает к слову по одной букве s₁, …, s_n и после каждой буквы просит Мишу сказать, на сколько увеличилось число различных непустых подстрок-палиндромов после приписывания. Две подстроки считаются различными, если они различаются как строки. Какие n чисел назовёт Миша, если он никогда не ошибается?

На вход подаётся строка s₁ … s_n из строчных латинских букв ‘a’ и ‘b’ (1 ≤ n ≤ 5 000 000).

Выведите n чисел подряд без пробелов. При этом i-е число должно равняться количеству различных подстрок-палиндромов префикса s₁ … s_i за вычетом этой же величины для s₁ … s_i−1. Первое число должно равняться единице.

Мы гарантируем, что жюри располагает решением на языке С++, укладывающимся в ограничение по времени хотя бы в два раза. Мы не гарантируем, что существует решение этой задачи на других языках (в том числе на Java).