|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||44||0||0||0.000%|
All characters appearing in this and following statements are fictitious. Any resemblance to real persons, living or dead, is purely coincidental.
This is an interactive problem.
Alfred and Margaret always play some weird string-guessing games when they spend a charming evening in the coffee shop "Donald's place".
This time, the rules are the following:
Margaret quickly noticed that Alfred always succeeds as the second player. She suspects there is a strategy that allows the second player to win regardless of what are the strings $S$ and $T$. Could you figure it out?
When your program starts, it must read two integers $N$ and $M$ from the standard input ($1 \leq N, M \leq 20\,000$).
Then $M$ rounds of the game follow. In the $i$-th round, you can ask up to five questions in the form "
<position1> <position2>". Here, the description of each position is either in the form "s $x$" where $1 \le x \le N$ ($x$-th character of the string $S$) or in the form "t $y$" where $1 \le y \le i$ ($y$-th character of the string $T$). The response from the jury program is "
Yes" if the characters on these positions are equal, and "
To finish each round, you must output the answer in the form "\$ $k$" where $k$ stands for the number of occurrences of string $S$ in the current string $T$. After that, the string $T$ will be automatically expanded by some unknown character, or the game finishes if it is the last round.
Do not forget to flush the standard output after each operation. Once you already reported all the $m$ required numbers, you should exit the program, otherwise the result of the judgement is undefined!
3 7 No Yes No Yes Yes Yes No No Yes Yes Yes
s 1 s 2 s 1 s 3 s 2 t 1 s 1 t 1 $ 0 s 2 t 2 $ 0 s 3 t 3 $ 1 s 2 t 4 s 1 t 4 $ 1 s 1 t 5 $ 1 s 2 t 6 $ 1 s 3 t 7 $ 2