Alice i Bob grają w serię gier przy użyciu stronniczej monety. Moneta daje orła z prawdopodobieństwem $p$, a reszkę z prawdopodobieństwem $1-p$.

W pojedynczej grze gracze rzucają monetą wielokrotnie. Po każdym rzucie, niech aktualna gra trwa dokładnie $m$ rzutów. Gra kończy się natychmiast, jeśli spełniony jest jeden z następujących warunków.

• Jeśli istnieje liczba całkowita $i \ge 1$ taka, że $2^i \mid m$, a ostatnie $2^i$ rzutów w bieżącej grze to

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

to Alice wygrywa grę.

• Jeśli istnieje liczba całkowita $i \ge 1$ taka, że $2^i \mid m$, a ostatnie $2^i$ rzutów w bieżącej grze to

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

to Bob wygrywa grę.

Gdy tylko gra się kończy, następna gra zaczyna się od następnego rzutu.

Mały Z zapisał pierwsze $n$ rzutów, ale niektóre znaki w zapisie zostały utracone i są zapisane jako ?. Każdy ? jest niezależnie równy $\mathrm{H}$ z prawdopodobieństwem $p$ i równy $\mathrm{T}$ z prawdopodobieństwem $1-p$. Znaki $\mathrm{H}$ i $\mathrm{T}$ w zapisie są ustalone.

Dane są $n$, $p$ oraz zapisany ciąg. Oblicz oczekiwaną liczbę gier wygranych przez Alice oraz oczekiwaną liczbę gier wygranych przez Boba wśród gier, które kończą się w ciągu pierwszych $n$ rzutów.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $n$ i liczbę rzeczywistą $p$ ($1 \le n \le 200000$, $0 < p < 1$). Liczba $p$ jest podana z dokładnie sześcioma cyframi po przecinku.

Drugi wiersz zawiera ciąg $s$ długości $n$. Każdy znak $s$ to $\mathrm{H}$, $\mathrm{T}$ lub ?.

Wyjście

Wypisz dwie liczby rzeczywiste: oczekiwaną liczbę gier wygranych przez Alice i oczekiwaną liczbę gier wygranych przez Boba.

Twoja odpowiedź zostanie uznana za poprawną, jeśli obie liczby mają błąd bezwzględny lub względny nie większy niż $10^{-6}$.

Przykład

Wejście 1

8 0.400000
??HHTTHH

Wyjście 1

0.720000000000000 1.120000000000000

Wejście 2

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

Wyjście 2

2.590680729436823 2.652863744188335

Uwagi

Dla pierwszego testu tylko pierwsze dwa rzuty są nieznane.

• Cztery uzupełnione zapisy to $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$ i $\mathrm{TTHHTTHH}$, z prawdopodobieństwami odpowiednio $0,16$, $0,24$, $0,24$, $0,36$.
• Ich liczby wygranych Alice/Boba to $(0,1)$, $(2,0)$, $(1,1)$ i $(0,2)$.
• Obliczając ważoną sumę otrzymujemy $(0,72,1,12)$, co jest zgodne z przykładowym wyjściem.

Dla drugiego testu ten zapis ma $16$ nieznanych rzutów.

• Uzupełnienie z $h$ orłami wśród nieznanych pozycji ma prawdopodobieństwo $0,314159^h(1-0,314159)^{16-h}$.
• Zsumowanie liczby wygranych Alice i Boba po wszystkich uzupełnieniach daje dwie wartości oczekiwane wypisane w przykładowym wyjściu.