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