方格著色遊戲 - Problema

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$, $\mathbf{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