Alice y Bob juegan una secuencia de partidas con una moneda sesgada. La moneda cae cara con probabilidad $p$, y sello con probabilidad $1-p$.

En una sola partida, los jugadores lanzan la moneda repetidamente. Después de cada lanzamiento, supongamos que la partida actual ha durado exactamente $m$ lanzamientos. La partida termina inmediatamente si se cumple una de las siguientes condiciones.

• Si existe un entero $i \ge 1$ tal que $2^i \mid m$, y los últimos $2^i$ lanzamientos de la partida actual son

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

entonces Alice gana la partida.

• Si existe un entero $i \ge 1$ tal que $2^i \mid m$, y los últimos $2^i$ lanzamientos de la partida actual son

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

entonces Bob gana la partida.

Tan pronto como una partida termina, la siguiente partida comienza con el siguiente lanzamiento.

Pequeño Z registró los primeros $n$ lanzamientos, pero algunos caracteres en el registro se perdieron y están escritos como ?. Cada ? es independientemente igual a $\mathrm{H}$ con probabilidad $p$, e igual a $\mathrm{T}$ con probabilidad $1-p$. Los caracteres $\mathrm{H}$ y $\mathrm{T}$ en el registro son fijos.

Dados $n$, $p$, y la cadena registrada, calcula el número esperado de partidas ganadas por Alice y el número esperado de partidas ganadas por Bob entre las partidas que terminan dentro de los primeros $n$ lanzamientos.

Entrada

La primera línea contiene un entero $n$ y un número real $p$ ($1 \le n \le 200000$, $0 < p < 1$). El número $p$ se proporciona con exactamente seis dígitos después del punto decimal.

La segunda línea contiene una cadena $s$ de longitud $n$. Cada carácter de $s$ es $\mathrm{H}$, $\mathrm{T}$ o ?.

Salida

Imprime dos números reales: el número esperado de partidas ganadas por Alice y el número esperado de partidas ganadas por Bob.

Tu respuesta será aceptada si ambos números tienen un error absoluto o relativo de a lo sumo $10^{-6}$.

Ejemplos

Entrada 1

8 0.400000
??HHTTHH

Salida 1

0.720000000000000 1.120000000000000

Entrada 2

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

Salida 2

2.590680729436823 2.652863744188335

Nota

Para la primera prueba, solo los primeros dos lanzamientos son desconocidos.

• Los cuatro registros completos son $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$, y $\mathrm{TTHHTTHH}$, con probabilidades $0.16,0.24,0.24,0.36$.
• Sus conteos de victorias de Alice/Bob son $(0,1)$, $(2,0)$, $(1,1)$, y $(0,2)$.
• Tomando la suma ponderada se obtiene $(0.72,1.12)$, coincidiendo con la salida de ejemplo.

Para la segunda prueba, este registro tiene $16$ lanzamientos desconocidos.

• Una completación con $h$ caras entre las posiciones desconocidas tiene probabilidad $0.314159^h(1-0.314159)^{16-h}$.
• Sumando los conteos de victorias de Alice y Bob sobre todas las completaciones se obtienen las dos esperanzas impresas en la salida de ejemplo.