题目描述

徐老师和石老师在玩一个博弈游戏：《回文字符串博弈》

游戏内容是这样的，游戏会给定一个初始字符串 $S$(仅由小写字母组成)

游戏双方每轮必须选择在字符串的开头或者结尾删除一个字符，然后交给另一个人进行下一轮游戏

在任意时刻如果某个玩家手里的字符串成为了回文串，则他就会失败

模式化的来说，每轮游戏的步骤依次如下：

1. 判定当前玩家手里的字符串是否为回文字符串，若是，则当前玩家失败，游戏结束
2. 当前玩家选择在字符串开头或者结尾删除一个字符，形式化的来说，如果字符串长度为 $len$，则当前玩家需要选择删除 $S[1]$ 或者 $S[len]$
3. 判定当前玩家手里的字符串是否为回文字符串，若是，则当前玩家失败，游戏结束
4. 本轮结束，由对手进行下一轮游戏

现在徐老师和石老师正在玩这个游戏，并且由徐老师进行第一轮游戏

假设他们两个足够聪明，在给定字符串 $S$ 的情况下请问谁会获胜？

P.S. 由于答案只有二选一，为了防止随机通过题目，每组数据包含多次询问，每次询问会给定一个区间 $[l,r]$，表示询问的是 $S[l \sim r]$ 这段字符串进行上述游戏的获胜者是谁

输入格式

输入第一行，包含一个整数 $len$ 表示字符串长度

输入第二行，包含一个长度为 $len$ 的字符串 $S$

输入第三行，包含一个整数 $Q$ 表示询问次数

接下来 $Q$ 行，每行包含两个整数 $l,r$ 表示一次询问

输出格式

输出共 $Q$ 行，对于每次询问输出获胜者，徐老师获胜则输出 Mr.Xu，石老师获胜则输出 Mr.Shi

数据范围

对于编号 $1 \sim 3$ 的测试数据保证 $len,Q \leq 20$

对于编号 $4 \sim 10$ 的测试数据保证 $1 \leq len,Q \leq 10^6$

对于所有数据保证 $1 \leq l \leq r \leq n$，且 $S$ 仅由小写字母组成

特别的，保证编号为 $4$ 的测试数据中 $S$ 为回文串

样例输入

7
rbnbnbr
3
1 3
3 5
1 6

样例输出

Mr.Xu
Mr.Shi
Mr.Shi

样例解释

对于第一次询问，询问 $rbn$ 的结果，以下为一种方案

1. 徐老师删除 $r$，变为 $bn$
2. 石老师删除 $b$，变为 $n$，此时判定石老师失败 可以发现不存在方案使得石老师获胜

对于第二次询问，询问 $nbn$ 的结果 徐老师拿到 $nbn$，判定徐老师失败，此时石老师直接获胜

对于第三次询问，询问 $rbnbnb$ 的结果，以下为一种方案

1. 徐老师删除 $r$ 就会失败，所以徐老师只能删除 $b$，变为 $rbnbn$
2. 石老师可以选择删除 $n$，变为 $rbnb$
3. 徐老师删除 $b$，变为 $rbn$
4. 石老师删除 $r$，变为 $bn$
5. 徐老师删除 $b$，变为 $n$，此时判定徐老师失败 可以发现不存在方案使得徐老师获胜