这是一个交互式问题。

Alfred 和 Margaret 在“唐纳德咖啡馆”（Donald’s place）消磨时光时，总是玩一些奇怪的猜字符串游戏。

这一次，规则如下：

• 第一位玩家写下一个预定义长度为 $N$ 的字符串 $S$。第一位玩家还有一个初始为空的字符串 $T$。两个字符串都只包含小写英文字母。
• 第二位玩家在整个游戏过程中无法看到这些字符串。但是，第二位玩家可以询问字符串中任意两个位置的字符是否相等。例如，一个询问可以是：“字符串 $S$ 的第二个字符是否等于字符串 $T$ 的第五个字符？”注意，也可以使用此询问来比较同一个字符串中的两个位置。
• 游戏共进行 $M$ 轮。在每一轮开始时，第一位玩家会在字符串 $T$ 的末尾添加一个字符。
• 当添加新字符时，第二位玩家最多可以提出五个询问。之后，第二位玩家必须说出字符串 $T$ 中有多少个子串等于字符串 $S$。

Margaret 很快注意到 Alfred 作为第二位玩家总是能成功。她怀疑存在一种策略，使得第二位玩家无论字符串 $S$ 和 $T$ 是什么都能获胜。你能找出这个策略吗？

输入格式

当程序开始时，必须从标准输入读取两个整数 $N$ 和 $M$ ($1 \le N, M \le 20\,000$)。

接下来进行 $M$ 轮游戏。在第 $i$ 轮中，你可以提出最多五个询问，格式为 “<position1> <position2>”。其中，每个位置的描述格式为 “s x”（表示字符串 $S$ 的第 $x$ 个字符，其中 $1 \le x \le N$）或 “t y”（表示字符串 $T$ 的第 $y$ 个字符，其中 $1 \le y \le i$）。如果这两个位置的字符相等，评测程序将返回 “Yes”，否则返回 “No”。

在每一轮结束时，你必须以 “$ k” 的格式输出答案，其中 $k$ 表示字符串 $S$ 在当前字符串 $T$ 中出现的次数。之后，字符串 $T$ 将自动扩展一个未知字符，如果是最后一轮，游戏则结束。

请记住在每次操作后刷新标准输出。一旦你报告了所有 $m$ 个要求的数字，就必须退出程序，否则判决结果将是未定义的！

样例

样例输入 1

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

样例输出 1

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

说明

在上面的样例中，字符串 $S$ 初始为 “aba”，字符串 $T$ 依次扩展的字符为 “a”、“b”、“a”、“c”、“a”、“b”、“a”。