Алиса и Боб играют серию игр с несимметричной монетой. Монета выпадает орлом с вероятностью $p$ и решкой с вероятностью $1-p$.

В каждой отдельной игре игроки подбрасывают монету многократно. После очередного броска, если текущая игра длится ровно $m$ бросков, игра немедленно заканчивается, если выполняется одно из следующих условий.

• Если существует целое число $i \ge 1$ такое, что $2^i \mid m$, и последние $2^i$ бросков текущей игры имеют вид

$$ \underbrace{\mathrm{H}\mathrm{H}\ldots \mathrm{H}}_{2^{i-1}} \underbrace{\mathrm{T}\mathrm{T}\ldots \mathrm{T}}_{2^{i-1}}, $$

то Алиса выигрывает игру.

• Если существует целое число $i \ge 1$ такое, что $2^i \mid m$, и последние $2^i$ бросков текущей игры имеют вид

$$ \underbrace{\mathrm{T}\mathrm{T}\ldots \mathrm{T}}_{2^{i-1}} \underbrace{\mathrm{H}\mathrm{H}\ldots \mathrm{H}}_{2^{i-1}}, $$

то Боб выигрывает игру.

Как только игра заканчивается, следующая игра начинается со следующего броска.

Маленькая Z записала первые $n$ бросков, но некоторые символы в записи были потеряны и записаны как ?. Каждый символ ? независимо оказывается $\mathrm{H}$ с вероятностью $p$ и $\mathrm{T}$ с вероятностью $1-p$. Символы $\mathrm{H}$ и $\mathrm{T}$ в записи фиксированы.

Даны $n$, $p$ и записанная строка. Вычислите математическое ожидание количества игр, выигранных Алисой, и математическое ожидание количества игр, выигранных Бобом, среди игр, завершающихся в пределах первых $n$ бросков.

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

Первая строка содержит целое число $n$ и вещественное число $p$ ($1 \le n \le 200000$, $0 < p < 1$). Число $p$ задаётся ровно с шестью знаками после десятичной точки.

Вторая строка содержит строку $s$ длины $n$. Каждый символ $s$ — это либо $\mathrm{H}$, либо $\mathrm{T}$, либо ?.

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

Выведите два вещественных числа: математическое ожидание количества игр, выигранных Алисой, и математическое ожидание количества игр, выигранных Бобом.

Ваш ответ будет принят, если оба числа имеют абсолютную или относительную погрешность не более $10^{-6}$.

Примеры

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

8 0.400000
??HHTTHH

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

0.720000000000000 1.120000000000000

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

20 0.314159
???H???T??T?????H???

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

2.590680729436823 2.652863744188335

Примечание

Для первого теста неизвестны только первые два броска.

• Четыре возможных завершённых записи: $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$, $\mathrm{TTHHTTHH}$ с вероятностями $0.16$, $0.24$, $0.24$, $0.36$.
• Количества побед Алисы и Боба в них: $(0,1)$, $(2,0)$, $(1,1)$, $(0,2)$.
• Взвешенная сумма даёт $(0.72, 1.12)$, что совпадает с примером вывода.

Для второго теста в записи $16$ неизвестных бросков.

• Вариант завершения с $h$ орлами среди неизвестных позиций имеет вероятность $0.314159^h(1-0.314159)^{16-h}$.
• Суммирование количества побед Алисы и Боба по всем вариантам завершения даёт два математических ожидания, напечатанных в примере вывода.