Alice et Bob jouent une suite de parties avec une pièce biaisée. La pièce tombe sur pile avec probabilité $p$, et sur face avec probabilité $1-p$. Dans une partie, les joueurs lancent la pièce de manière répétée. Après chaque lancer, supposons que la partie en cours ait duré exactement $m$ lancers. La partie se termine immédiatement si l'une des conditions suivantes est satisfaite.

• S'il existe un entier $i \ge 1$ tel que $2^i \mid m$, et les $2^i$ derniers lancers de la partie en cours sont

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

alors Alice gagne la partie.

• S'il existe un entier $i \ge 1$ tel que $2^i \mid m$, et les $2^i$ derniers lancers de la partie en cours sont

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

alors Bob gagne la partie.

Dès qu'une partie se termine, la partie suivante commence avec le lancer suivant.

Petit Z a enregistré les $n$ premiers lancers, mais certains caractères de l'enregistrement ont été perdus et sont écrits comme ?. Chaque ? est indépendamment égal à $\mathrm{H}$ avec probabilité $p$, et égal à $\mathrm{T}$ avec probabilité $1-p$. Les caractères $\mathrm{H}$ et $\mathrm{T}$ dans l'enregistrement sont fixés.

Étant donné $n$, $p$, et la chaîne enregistrée, calculez le nombre espéré de parties gagnées par Alice et le nombre espéré de parties gagnées par Bob parmi les parties qui se terminent dans les $n$ premiers lancers.

Entrée

La première ligne contient un entier $n$ et un nombre réel $p$ ($1 \le n \le 200000$, $0 < p < 1$). Le nombre $p$ est donné avec exactement six chiffres après la virgule.

La deuxième ligne contient une chaîne $s$ de longueur $n$. Chaque caractère de $s$ est soit $\mathrm{H}$, soit $\mathrm{T}$, soit ?.

Sortie

Affichez deux nombres réels : le nombre espéré de parties gagnées par Alice et le nombre espéré de parties gagnées par Bob.

Votre réponse sera acceptée si les deux nombres ont une erreur absolue ou relative d'au plus $10^{-6}$.

Exemples

Entrée 1

8 0.400000
??HHTTHH

Sortie 1

0.720000000000000 1.120000000000000

Entrée 2

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

Sortie 2

2.590680729436823 2.652863744188335

Remarque

Pour le premier test, seuls les deux premiers lancers sont inconnus.

• Les quatre enregistrements complets sont $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$ et $\mathrm{TTHHTTHH}$, avec probabilités $0.16, 0.24, 0.24, 0.36$.
• Leurs nombres de victoires Alice/Bob sont $(0,1)$, $(2,0)$, $(1,1)$ et $(0,2)$.
• La somme pondérée donne $(0.72, 1.12)$, ce qui correspond à l'exemple de sortie.

Pour le second test, cet enregistrement a $16$ lancers inconnus.

• Un achèvement avec $h$ faces parmi les positions inconnues a une probabilité $0.314159^h(1-0.314159)^{16-h}$.
• La somme des nombres de victoires d'Alice et de Bob sur tous les achèvements donne les deux espérances affichées dans l'exemple de sortie.