Вам надано двійковий рядок довжиною \(n\).

Ваше завдання полягає в тому, щоб обчислити для кожного \(k\) між \(1…n−1\) кількість способів, якими ми можемо вибрати дві позиції \(i\) та \(j\) так, щоб \(i−j=k\) і в обох позиціях є одиничний біт.

Обмеження

• \(2≤n≤2⋅10^5\)

Формат вхідних даних

Єдиний вхідний рядок містить рядок, який складається лише з символів 0 та 1.

Формат вихідних даних

Для кожної відстані \(k\) між \(1…n−1\) виведіть кількість способів, якими ми можемо вибрати дві таких позиції.

Приклад вхідних даних

1001011010

Приклад вихідних даних

1 2 3 0 2 1 0 1 0