D. Считаем хорошие подстроки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Строка называется хорошей, если после объединения всех последовательных равных символов в один символ получившаяся строка является палиндромом. Например, «aabba» является хорошей, потому что после объединения одинаковых символов она станет строкой «aba».

Вам дана строка, посчитайте две величины:

  1. количество хороших ее подстрок четной длины;
  2. количество хороших ее подстрок нечетной длины.
Входные данные

В первой строке записана единственная строка длины n (1 ≤ n ≤ 105). Каждый символ этой строки равен либо 'a', либо 'b'.

Выходные данные

Выведите два целых числа через пробел: количество хороших подстрок четной длины и количество хороших подстрок нечетной длины.

Примеры
Входные данные
bb
Выходные данные
1 2
Входные данные
baab
Выходные данные
2 4
Входные данные
babb
Выходные данные
2 5
Входные данные
babaa
Выходные данные
2 7
Примечание

В первом примере есть три хороших подстроки («b», «b», и «bb»). Длина одной из них — четная, длина двух других — нечетная.

Во втором примере есть шесть хороших подстрок («b», «a», «a», «b», «aa», «baab»). Две из них имеют четную длину, остальные четыре — нечетную длину.

В третьем примере есть семь хороших подстрок («b», «a», «b», «b», «bb», «bab», «babb»). Две из них имеют четную длину, остальные пять — нечетную длину.

Определения

Подстрока s[l, r] (1 ≤ l ≤ r ≤ n) строки s = s1s2... sn — это строка slsl + 1... sr.

Строка s = s1s2... sn является палиндромом, если она равна строке snsn - 1... s1.