Aho

Time limit1sMemory limit512 MB

Summary

After each character appended to hidden T, ask at most five equality queries, then report how many substrings of T equal hidden S.

Level: Hard9 of 10
Topics: String, String matching, Implementation
Solved: No attempts yet

Problem

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:

The first player writes down a string $S$ of a predefined length $N$ . The first player also has a string $T$ that is initially empty. Both strings contain only lowercase English letters.
The second player cannot see these strings during the whole game. However, the second player is allowed to ask whether the characters on any pair of positions in any of the strings are equal. For example, a question can look like the following: "Is the second character of string $S$ equal to the fifth character of string $T$ ?" Note that it is also allowed to compare two positions of the same string using this question.
The game is played in $M$ rounds. At the start of each round, the first player adds a single character to the end of string $T$ .
When a new character is added, the second player can ask no more than five questions. After that, the second player must say how many substrings of string $T$ are equal to string $S$ .

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 the strings $S$ and $T$ are. Could you figure it out?

Examples1

Example 1

Input

3 7
No
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes
Yes

Expected output

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