You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

关桑 和 大牛正在玩一个新游戏。一开始，关桑 有一张纸条上面写着一个由小写字母组成的字符串。在每一轮中，拿着纸条的玩家必须从纸条的开头或结尾撕下一个字符，然后把它传给另一个玩家。如果在任何时刻，纸条上的字符串是一个回文串，那么拿着纸条的玩家就输了。注意，无论玩家在撕下纸条上的字符之前还是之后，都被认为拿着纸条。一个长度为 $n$ 的字符串被认为是一个回文串，如果对于所有整数 $i$ 从 $1$ 到 $n$，$s_i = s_{n-i+1}$。

然而，当 关桑 找到纸条时，他发现有人在这张纸条上玩过。由于 关桑 和 大牛都很聪明，他们总是会选择最好的方法来赢得比赛，他们想知道谁会赢得比赛，所以他们求助于你。具体来说，给定一个长度为 $n$ 的字符串，你需要回答 $q$ 个查询，每个查询由两个整数 $l$ 和 $r$ 描述，这意味着你必须确定如果 关桑 和 大牛在字符串 $s[l]s[l+1]…s[r]$ 上玩上述游戏，谁会赢得比赛。

输入格式

• 第一行包含一个整数 $n$ 表示字符串的长度，和一个整数 $q$，表示查询的数量。
• 第二行包含一个长度为 $n$ 的字符串 $s$
• 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$，描述一个查询。

输出格式

对于每个查询，输出一个结果，表示如果关桑赢了比赛，输出 Guan，如果是大牛赢得了比赛，输出 Cow

样例输入1

7 3
potatop
1 3
3 5
1 6

样例输出1

Guan
Cow
Cow

数据范围与约定

• 对于 $30\%$ 的数据，保证 $n, q \leq 20$
• 对于另外 $10\%$ 的数据，保证整个串都是回文串
• 对于 $100\%$ 的数据，$1 \leq n,q \leq 10^6, 1 \leq l \leq r \leq n$