Alice 和 Bob 使用一枚偏倚硬幣進行一系列遊戲。硬幣擲出正面的機率為 $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}}, $$
則 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 贏得該遊戲。
一旦遊戲結束，下一場遊戲就從下一次擲幣開始。
小 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$ 給出恰好六位小數。
第二行包含一個長度為 $n$ 的字串 $s$。$s$ 的每個字符是 $\mathrm{H}$、$\mathrm{T}$ 或 ?。
輸出格式
輸出兩個實數：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
說明
對於第一個測試，只有前兩次擲幣是未知的。
- 四個完整的記錄為 $\mathrm{HHHHTTHH}$、$\mathrm{HTHHTTHH}$、$\mathrm{THHHTTHH}$ 和 $\mathrm{TTHHTTHH}$，機率分別為 $0.16,0.24,0.24,0.36$。
- 它們的 Alice/Bob 獲勝次數分別為 $(0,1)$、$(2,0)$、$(1,1)$ 和 $(0,2)$。
- 加權求和得到 $(0.72,1.12)$，與範例輸出一致。
對於第二個測試，該記錄有 $16$ 個未知擲幣。
- 在未知位置中有 $h$ 個正面的完成結果的機率為 $0.314159^h(1-0.314159)^{16-h}$。
- 對所有完成結果的 Alice 和 Bob 獲勝次數求和，得到範例輸出中給出的兩個期望值。