题目描述

Sam 和 Paul 在玩一个博弈游戏：《回文字符串博弈》。

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

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

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

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

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

现在 Sam 和 Paul 正在玩这个游戏，并且由 Sam 进行第一轮游戏。

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

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

输入格式

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

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

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

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

输出格式

输出共 $Q$ 行，对于每次询问输出获胜者，Sam 获胜则输出 Sam，Paul获胜则输出 Paul。

输入输出样例 #1

输入 #1

7
rbnbnbr
3
1 3
3 5
1 6

输出 #1

Sam
Paul
Paul

说明/提示

数据范围

对于编号 $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$ 为回文串。

样例解释

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

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

对于第二次询问，询问 $nbn$ 的结果。Sam 拿到 $nbn$，判定 Sam 失败，此时 Paul 直接获胜。

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

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