앨리스와 밥은 편향된 동전을 사용하여 일련의 게임을 한다. 동전은 앞면이 $p$의 확률로, 뒷면이 $1-p$의 확률로 나온다.

한 게임에서, 두 플레이어는 동전을 반복적으로 던진다. 각 던진 후, 현재 게임이 정확히 $m$번 던진 상태라고 가정하자. 다음 조건 중 하나가 만족되면 게임은 즉시 종료된다.

• 만약 $2^i \mid m$인 정수 $i \ge 1$이 존재하고, 현재 게임의 마지막 $2^i$번 던진 결과가

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

이면 앨리스가 게임에서 승리한다.

• 만약 $2^i \mid m$인 정수 $i \ge 1$이 존재하고, 현재 게임의 마지막 $2^i$번 던진 결과가

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

이면 밥이 게임에서 승리한다.

게임이 종료되는 즉시, 다음 던진 결과로 다음 게임이 시작된다.

꼬마 Z는 처음 $n$번의 던진 결과를 기록했지만, 기록의 일부 문자가 손실되어 ?로 쓰여 있다. 각 ?는 다른 것과 독립적으로 확률 $p$로 $\mathrm{H}$, 확률 $1-p$로 $\mathrm{T}$이다. 기록에 있는 $\mathrm{H}$와 $\mathrm{T}$ 문자는 고정되어 있다.

$n$, $p$, 그리고 기록된 문자열이 주어졌을 때, 처음 $n$번의 던진 결과 내에서 종료된 게임 중 앨리스가 승리한 게임 수의 기댓값과 밥이 승리한 게임 수의 기댓값을 계산하라.

입력

첫 번째 줄에는 정수 $n$과 실수 $p$가 주어진다 ($1 \le n \le 200000$, $0 < p < 1$). $p$는 소수점 아래 정확히 여섯 자리까지 주어진다.

두 번째 줄에는 길이 $n$의 문자열 $s$가 주어진다. $s$의 각 문자는 $\mathrm{H}$, $\mathrm{T}$, 또는 ?이다.

출력

두 개의 실수를 출력한다: 앨리스가 승리한 게임 수의 기댓값과 밥이 승리한 게임 수의 기댓값.

두 숫자 모두 절대 오차 또는 상대 오차가 $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$이다.
• 각각의 앨리스/밥 승리 횟수는 $(0,1)$, $(2,0)$, $(1,1)$, $(0,2)$이다.
• 가중합을 구하면 $(0.72,1.12)$가 되어 예제 출력과 일치한다.

두 번째 테스트의 경우, 이 기록에는 $16$개의 알 수 없는 던진 결과가 있다.

• 알 수 없는 위치 중 앞면이 $h$개인 완성 결과의 확률은 $0.314159^h(1-0.314159)^{16-h}$이다.
• 모든 완성 결과에 대해 앨리스와 밥의 승리 횟수를 합하면 예제 출력에 출력된 두 기댓값이 나온다.