Tokitsukaze is playing with CSL a game based on a string
S
1..n![]()
![]()
which only contains lowercase letters and whose length is
n![]()
.
A string is palindromic if and only if it reads the same backward as forward, such as "madam" and "racecar". Before the game starts, Tokitsukaze will select a palindromic substring of
S![]()
, denoted as
S
a..b![]()
![]()
, and CSL will select a palindromic substring, denoted as
S
c..d![]()
![]()
, too.
There is also a string
P![]()
that is empty at the beginning of the game. Then at every second, a character will be appended to the end of
P![]()
automatically, where the character is randomly chosen from all possible lowercase letters (i.e. 'a' to 'z'), each with the same probability
1
26![]()
![]()
![]()
. The game ends when both
S
a..b![]()
![]()
and
S
c..d![]()
![]()
become substrings of
P![]()
.
Let
E(S
a..b
)![]()
be the expected length of
P![]()
when
S
a..b![]()
firstly becomes a substring of
P![]()
, and
E(S
c..d
)![]()
be the similar expected value for
S
c..d![]()
![]()
. The winner of the game will be the one with a lower expected value for his or her choice. In case of a tie, when
E(S
a..b
)![]()
equals to
E(S
c..d
)![]()
, the game is a draw.
Now, they will play this game with the same string
S![]()
for
q![]()
times, and Tokitsukaze will inform you of their choices in each game. Can you predict for her the result of each game?