Alice và Bob chơi một chuỗi các ván chơi với một đồng xu lệch. Đồng xu ra mặt ngửa với xác suất $p$, và ra mặt sấp với xác suất $1-p$. Trong một ván chơi, các người chơi tung đồng xu liên tục. Sau mỗi lần tung, giả sử ván chơi hiện tại đã kéo dài đúng $m$ lần tung. Ván chơi kết thúc ngay lập tức nếu một trong các điều kiện sau được thỏa mãn.

• Nếu tồn tại số nguyên $i \ge 1$ sao cho $2^i \mid m$, và $2^i$ lần tung cuối cùng của ván chơi hiện tại là

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

thì Alice thắng ván chơi.

• Nếu tồn tại số nguyên $i \ge 1$ sao cho $2^i \mid m$, và $2^i$ lần tung cuối cùng của ván chơi hiện tại là

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

thì Bob thắng ván chơi.

Ngay khi một ván chơi kết thúc, ván chơi tiếp theo bắt đầu với lần tung tiếp theo.

Little Z đã ghi lại $n$ lần tung đầu tiên, nhưng một số ký tự trong bản ghi bị mất và được viết là ?. Mỗi ? độc lập có giá trị $\mathrm{H}$ với xác suất $p$, và có giá trị $\mathrm{T}$ với xác suất $1-p$. Các ký tự $\mathrm{H}$ và $\mathrm{T}$ trong bản ghi là cố định.

Cho trước $n$, $p$, và xâu đã ghi, tính số ván chơi kỳ vọng mà Alice thắng và số ván chơi kỳ vọng mà Bob thắng trong số các ván chơi kết thúc trong $n$ lần tung đầu tiên.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $n$ và một số thực $p$ ($1 \le n \le 200000$, $0 < p < 1$). Số $p$ được cho với chính xác sáu chữ số sau dấu thập phân.

Dòng thứ hai chứa một xâu $s$ có độ dài $n$. Mỗi ký tự của $s$ là $\mathrm{H}$, $\mathrm{T}$, hoặc ?.

Dữ liệu ra

In ra hai số thực: số ván chơi kỳ vọng Alice thắng và số ván chơi kỳ vọng Bob thắng.

Kết quả của bạn sẽ được chấp nhận nếu cả hai số có sai số tuyệt đối hoặc tương đối không quá $10^{-6}$.

Ví dụ

Dữ liệu vào 1

8 0.400000
??HHTTHH

Dữ liệu ra 1

0.720000000000000 1.120000000000000

Dữ liệu vào 2

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

Dữ liệu ra 2

2.590680729436823 2.652863744188335

Ghi chú

Đối với test đầu tiên, chỉ có hai lần tung đầu tiên là chưa biết.

• Bốn bản ghi hoàn chỉnh là $\mathrm{HHHHTTHH}$, $\mathrm{HTHHTTHH}$, $\mathrm{THHHTTHH}$, và $\mathrm{TTHHTTHH}$, với các xác suất $0.16,0.24,0.24,0.36$.
• Số ván thắng của Alice/Bob tương ứng là $(0,1)$, $(2,0)$, $(1,1)$, và $(0,2)$.
• Lấy tổng có trọng số cho $(0.72,1.12)$, khớp với đầu ra mẫu.

Đối với test thứ hai, bản ghi này có $16$ lần tung chưa biết.

• Một cách hoàn chỉnh với $h$ mặt ngửa trong số các vị trí chưa biết có xác suất $0.314159^h(1-0.314159)^{16-h}$.
• Tính tổng số ván thắng của Alice và Bob trên tất cả các cách hoàn chỉnh cho hai kỳ vọng được in trong đầu ra mẫu.