Tokitsukaze is playing with CSL a game based on a string
S1..nwhich 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
Sa..b, and CSL will select a palindromic substring, denoted as
Sc..d, too.
There is also a string
Pthat is empty at the beginning of the game. Then at every second, a character will be appended to the end of
Pautomatically, where the character is randomly chosen from all possible lowercase letters (i.e. 'a' to 'z'), each with the same probability
126. The game ends when both
Sa..band
Sc..dbecome substrings of
P.
Let
E(Sa..b)be the expected length of
Pwhen
Sa..bfirstly becomes a substring of
P, and
E(Sc..d)be the similar expected value for
Sc..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(Sa..b)equals to
E(Sc..d), the game is a draw.
Now, they will play this game with the same string
Sfor
qtimes, and Tokitsukaze will inform you of their choices in each game. Can you predict for her the result of each game?