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 的获胜局数，得到样例输出中打印的两个期望值。