正方形涂色游戏 - Problem

MITIT 俱乐部经常举办“社交聚会”，这些有趣的活动旨在让俱乐部成员进行社交，并从繁重的学业、题目编写或竞赛组织工作中放松一下。现场会提供零食和游戏。但这些游戏可能有点奇怪……

MITIT 俱乐部的成员 Amy 和 Aimee 正在玩她们发明的一种新棋盘游戏！

棋盘由一行 $N$ 个方格组成，每个方格的颜色为红色、绿色或白色。玩家还商定了一个参数 $K$（满足 $0 \le K \le \min(N-1, 7)$），这是一个非负整数。Amy 先手，两人轮流行动。

在每一轮中，玩家按照以下步骤进行操作：

选择一个包含奇数个方格的子集 $S$，其中所有方格必须为白色，且 $S$ 中任意两个方格之间的距离（即它们坐标的绝对差）不超过 $K$。

特别地，选择恰好一个白色方格作为 $S$ 总是合法的，且 $|S|$ 不可能超过 $K + 1$（当然，$|S|$ 也必须是奇数）。
将 $S$ 中的所有方格涂成红色，或者将它们全部涂成绿色，前提是红色方格不能与绿色方格相邻。对于某些 $S$ 的选择，这一步可能无法完成；在这种情况下，玩家必须选择不同的 $S$。

第一个无法进行合法操作的玩家输掉比赛。

给定 Amy 第一次移动前的棋盘状态（保证此时没有红色方格与绿色方格相邻），若双方均采取最优策略，确定哪位玩家获胜。

输入包含多个测试用例。第一行包含一个整数 $T$ ($1 \le T \le 5 \cdot 10^4$)，表示测试用例的数量。

每个测试用例的第一行包含 $N$ 和 $K$ ($1 \le N \le 2\cdot 10^5$, $0 \le K \le \min(N-1, 7)$)。

每个测试用例的第二行包含一个长度为 $N$ 的字符串，描述棋盘的初始状态。每个字符为 R（红色）、G（绿色）或 W（白色）。保证初始状态下没有 R 与 G 相邻。

保证所有测试用例的 $N$ 之和不超过 $4 \cdot 10^5$。

对于每个测试用例，输出 Amy 或 Aimee，表示获胜的玩家。

5
5 4
WWWWW
16 3
RRRRWGGGGGWRRRRR
6 5
WWWWWW
12 0
WWWWRRWGGGWW
13 7
WRRWWGWRWRWWW

Amy
Aimee
Aimee
Amy
Amy

在第一个样例中，Amy 可以通过选择整个棋盘作为 $S$ 并将其全部涂成红色来获胜。

在第二个样例中，Amy 在第一轮无法进行合法操作，她直接输掉比赛。

在第三个样例中，无论 Amy 第一轮如何操作，Aimee 总能在她的回合将整个棋盘涂成同一种颜色，从而赢得比赛。

QOJ.ac