Alice and Bob play a sequence of games with a biased coin. The coin lands heads with probability $p$, and tails with probability $1-p$. In a single game, the players toss the coin repeatedly. After each toss, suppose that the current game has lasted exactly $m$ tosses. The game ends immediately if one of the following conditions is satisfied.

• If there exists an integer $i \ge 1$ such that $2^i \mid m$, and the last $2^i$ tosses of the current game are

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

then Alice wins the game.

• If there exists an integer $i \ge 1$ such that $2^i \mid m$, and the last $2^i$ tosses of the current game are

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

then Bob wins the game.

As soon as a game ends, the next game starts with the next toss.

Little Z recorded the first $n$ tosses, but some characters in the record were lost and are written as ?. Each ? is independently equal to $\mathrm{H}$ with probability $p$, and equal to $\mathrm{T}$ with probability $1-p$. The characters $\mathrm{H}$ and $\mathrm{T}$ in the record are fixed.

Given $n$, $p$, and the recorded string, compute the expected number of games won by Alice and the expected number of games won by Bob among the games that end within the first $n$ tosses.

Input

The first line contains an integer $n$ and a real number $p$ ($1 \le n \le 200000$, $0 < p < 1$). The number $p$ is given with exactly six digits after the decimal point.

The second line contains a string $s$ of length $n$. Each character of $s$ is either $\mathrm{H}$, $\mathrm{T}$, or ?.

Output

Print two real numbers: the expected number of games won by Alice and the expected number of games won by Bob.

Your answer will be accepted if both numbers have an absolute or relative error of at most $10^{-6}$.

Examples

Input 1

8 0.400000
??HHTTHH

Output 1

0.720000000000000 1.120000000000000

Input 2

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

Output 2

2.590680729436823 2.652863744188335

Note

For the first test, only the first two tosses are unknown.

• The four completed records are $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$, and $\mathrm{TTHHTTHH}$, with probabilities $0.16,0.24,0.24,0.36$.
• Their Alice/Bob win counts are $(0,1)$, $(2,0)$, $(1,1)$, and $(0,2)$.
• Taking the weighted sum gives $(0.72,1.12)$, matching the sample output.

For the second test, this record has $16$ unknown tosses.

• A completion with $h$ heads among the unknown positions has probability $0.314159^h(1-0.314159)^{16-h}$.
• Summing the Alice and Bob win counts over all completions gives the two expectations printed in the sample output.