Klub MITIT regularnie organizuje „spotkania towarzyskie”, czyli wydarzenia, podczas których członkowie klubu mogą się zintegrować i odpocząć od nauki, układania zadań czy organizacji konkursów. Zapewnione są przekąski i gry. Jednak gry bywają nieco dziwne...
Amy i Aimee, członkinie klubu MITIT, grają w nową grę planszową, którą same wymyśliły!
Plansza składa się z rzędu $N$ pól, z których każde jest koloru czerwonego, zielonego lub białego. Gracze ustalili również parametr $K$ (spełniający $0 \le K \le \min(N-1, 7)$), będący nieujemną liczbą całkowitą. Amy wykonuje ruch jako pierwsza i gracze wykonują ruchy na zmianę.
W każdej turze gracz wykonuje ruch zgodnie z poniższą procedurą:
Wybierz podzbiór $S$ składający się z nieparzystej liczby pól, z których wszystkie są białe, taki że odległość między dowolnymi dwoma polami (tj. wartość bezwzględna różnicy ich współrzędnych) w $S$ nie przekracza $K$.
W szczególności, zawsze dopuszczalne jest, aby $S$ zawierało dokładnie jedno białe pole, i nigdy nie jest możliwe, aby $|S|$ przekroczyło $K + 1$ (oczywiście $|S|$ musi być również nieparzyste).
Pokoloruj wszystkie pola w $S$ na czerwono lub pokoloruj wszystkie z nich na zielono, pod warunkiem, że żadne czerwone pole nie może nigdy sąsiadować z zielonym. Może się zdarzyć, że wykonanie tego kroku jest niemożliwe dla niektórych poprawnych wyborów $S$; w takim przypadku gracz jest zmuszony wybrać $S$ inaczej.
Gracz, który jako pierwszy nie może wykonać poprawnego ruchu, przegrywa.
Mając dany stan planszy przed pierwszym ruchem Amy, w którym żadne czerwone pole nie sąsiaduje z zielonym, określ, który gracz wygra, jeśli oboje grają optymalnie.
Wejście
Wejście składa się z kilku przypadków testowych. Pierwsza linia zawiera liczbę całkowitą $T$ ($1 \le T \le 5 \cdot 10^4$): liczbę przypadków testowych.
Pierwsza linia każdego przypadku testowego zawiera $N$ oraz $K$ ($1 \le N \le 2\cdot 10^5$, $0 \le K \le \min(N-1, 7)$).
Druga linia każdego przypadku testowego zawiera ciąg $N$ znaków opisujących początkowy stan planszy. Każdy znak to R (czerwony), G (zielony) lub W (biały). Gwarantuje się, że żadne R nie sąsiaduje z G.
Gwarantuje się, że suma $N$ we wszystkich przypadkach testowych nie przekracza $4 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego wypisz Amy lub Aimee, wskazując gracza, który wygra.
Punktacja
- ($15$ punktów) $N \le 10$.
- ($15$ punktów) Żadne dwa białe pola nie sąsiadują ze sobą w stanie początkowym.
- ($10$ punktów) Stan początkowy jest całkowicie biały, a $K = 0$.
- ($20$ punktów) $K = 0$.
- ($40$ punktów) Brak dodatkowych ograniczeń.
Przykład
Wejście 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
Wyjście 1
Amy Aimee Aimee Amy Amy
Uwagi
W pierwszym przypadku testowym Amy może wygrać, wybierając $S$ jako całą planszę i kolorując ją w całości na czerwono w swoim pierwszym ruchu.
W drugim przypadku Amy nie może wykonać poprawnego ruchu w swojej pierwszej turze i przegrywa natychmiast.
W trzecim przypadku, niezależnie od tego, co Amy zrobi w swoim pierwszym ruchu, Aimee zawsze jest w stanie pokolorować całą planszę na ten sam kolor w swojej turze, tym samym wygrywając grę.