시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

Alice and Bob have each picked a string containing only heads and tails.  Then a fair coin is flipped until a sequence of consecutive flips matches one or both of the strings.  Alice wins if her string appears first, and Bob wins if his appears first.  It's possible that both of their strings appear at the same time.  In that case the game is a tie.

Given the two strings, what is the probability of these three outcomes?

입력

The first line of input is Alice's string, and the second line is Bob's. These strings contain only Hs and Ts, and their lengths are between 1 and 20, inclusive.

출력

The output consists of three lines, each of which contains a single real number.  They should be the probability that Alice wins, the probability that Bob wins, and the probability of a tie.

An answer will be accepted if it differs from the correct answer by at most $10^{-8}$.

예제 입력 1

H
T

예제 출력 1

0.500000000000
0.500000000000
0.000000000000

예제 입력 2

HHT
HTH

예제 출력 2

0.666666666667
0.333333333333
0.000000000000

예제 입력 3

THH
HH

예제 출력 3

0.000000000000
0.250000000000
0.750000000000