Alice と Bob は、偏りのあるコインで一連のゲームを行う。コインは確率 $p$ で表、確率 $1-p$ で裏が出る。

1 回のゲームでは、プレイヤーはコインを繰り返し投げる。各投げの後、現在のゲームがちょうど $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}}, $$

であるならば、Alice がゲームに勝つ。

• ある整数 $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}}, $$

であるならば、Bob がゲームに勝つ。

ゲームが終了するとすぐに、次の投げから次のゲームが始まる。

Little Z は最初の $n$ 回の投げの記録を残したが、記録の一部の文字が失われて ? と書かれている。各 ? は独立に確率 $p$ で $\mathrm{H}$、確率 $1-p$ で $\mathrm{T}$ となる。記録内の $\mathrm{H}$ と $\mathrm{T}$ の文字は確定している。

$n$, $p$ および記録された文字列が与えられたとき、最初の $n$ 回の投げの中で終了するゲームのうち、Alice が勝つゲームの数の期待値と Bob が勝つゲームの数の期待値を計算せよ。

入力

最初の行には整数 $n$ と実数 $p$ が含まれる ($1 \le n \le 200000$, $0 < p < 1$)。$p$ は小数点以下ちょうど 6 桁で与えられる。

2 行目には長さ $n$ の文字列 $s$ が含まれる。$s$ の各文字は $\mathrm{H}$, $\mathrm{T}$, ? のいずれかである。

出力

2 つの実数を出力せよ。Alice が勝つゲームの数の期待値と Bob が勝つゲームの数の期待値である。

両方の数について絶対誤差または相対誤差が $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

注記

最初のテストケースでは、最初の 2 回の投げのみが未知である。

• 完全な記録は $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$, $\mathrm{TTHHTTHH}$ の 4 通りで、確率はそれぞれ $0.16,0.24,0.24,0.36$ である。
• それぞれの Alice/Bob の勝利数は $(0,1)$, $(2,0)$, $(1,1)$, $(0,2)$ である。
• 重み付き和を取ると $(0.72,1.12)$ となり、サンプル出力と一致する。

2 番目のテストケースでは、この記録には 16 個の未知の投げがある。

• 未知の位置のうち $h$ 個が表であるような補完は、確率 $0.314159^h(1-0.314159)^{16-h}$ を持つ。
• すべての補完について Alice と Bob の勝利数を合計すると、サンプル出力に示された 2 つの期待値になる。