Кавовий автомат

Limits: 2 sec., 512 MiB

Зеник недавно влаштувався на роботу в офіс і от йому прийшло перше неочікуване завдання: знайти кавовий автомат. Офіс Зеника доволі непросторий і розташований у довгому коридорі з \(n\) секцій однакової ширини. У кожній секції може бути робоче місце, кавовий автомат або порожній простір. Зеник ще не знає, яке з робочих місць належить йому, але багато ходити він не любить. Тому він попросив вас допомогти йому знайти відстань до найближчого кавового автомата для кожного робочого місця. Робоче місце в коридорі позначено англійською буквою W, а кавовий автомат — буквою C. Символ . позначає, що в проході немає ні робочого місця, ні автомату. Відстань між сусідніми секціями дорівнює одному метру.

Input

У єдиному рядку вхідних даних задано рядок \(s\), що складається лише із символів W, C та ., що позначають робоче місце, кавовий автомат та вільний прохід відповідно.

Output

Виведіть послідовність чисел, що відповідають мінімальній відстані (у метрах) до найближчого кавового автомата для кожного робочого місця, у тому ж порядку у якому ці робочі місця розташовані в рядку \(s\) (зліва направо).

Constraints

\(2 \le |s| \le 1000\).

Гарантовано, що існує хоча б один кавовий автомат та хоча б одне робоче місце.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 10 балів: кількість робочих місць рівна 1,

• 15 балів: кількість кавових автоматів рівна 1,

• 20 балів: усі робочі місця знаходяться лівіше від усіх кавових автоматів,

• 53 бали: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Samples

Input (stdin) сopy	Output (stdout) сopy
W...C......W	4 7

Input (stdin) сopy	Output (stdout) сopy
C...W......C	4

Notes

Відстань між робочим місцем і кавовим автоматом визначається як кількість секцій між ними. У першому випадку є лише один автомат. У другому випадку Зенику оптимально йти до крайнього лівого кавового автомату. Відстань між ним та автоматом рівна 4.