正方形塗り分けゲーム - 题目

MITITクラブでは定期的に「ソーシャルミキサー」が開催されています。これはクラブメンバーが交流し、学業や問題作成、コンテスト運営の合間に息抜きをするための楽しいイベントです。軽食やゲームが用意されていますが、そのゲームは少し変わったものです……。

MITITクラブのメンバーであるAmyとAimeeは、自分たちで考案した新しいボードゲームで遊んでいます！

ボードは $N$ 個のマスが1列に並んだもので、各マスは赤、緑、または白に塗られています。プレイヤーは非負整数であるパラメータ $K$ ($0 \le K \le \min(N-1, 7)$) をあらかじめ決めておきます。Amyが先攻で、交互に手番を行います。

各手番において、プレイヤーは以下の手順に従って手を動かします。

すべてが白であるマスからなる、要素数が奇数の部分集合 $S$ を選択します。このとき、$S$ に含まれる任意の2つのマスの距離（すなわち、座標の絶対差）が $K$ を超えてはなりません。

特に、$S$ がちょうど1つの白いマスからなることは常に許容されます。また、$|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)$) が含まれます。

各テストケースの2行目には、ボードの初期状態を表す $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$ としてボード全体（5つの白いマス）を選択し、すべてを赤く塗ることで勝利できます。

2番目のサンプルでは、ボード上の白いマスは R と G に挟まれており、どの白いマスを選んでも隣接する R または G との条件に抵触するため、Amyは最初の手番で合法的な手番を行うことができず、即座に敗北します。

3番目のサンプルでは、ボード全体が白であり、$K=5$ です。Amyが最初の手番でどのような行動をとっても、残されたボードの状態に対してAimeeが勝利する戦略をとることができます。

QOJ.ac