El club MITIT organiza regularmente "reuniones sociales", que son eventos divertidos destinados a que los miembros del club socialicen y se tomen un descanso de las tareas escolares, la redacción de problemas o la organización de concursos. Se ofrecen bocadillos y juegos. Pero los juegos pueden ser un poco extraños...
Amy y Aimee, miembros del club MITIT, están jugando un nuevo juego de mesa que inventaron.
El tablero consiste en una fila de $N$ casillas, cada una coloreada de rojo, verde o blanco. Los jugadores también han acordado un parámetro $K$ (que satisface $0 \le K \le \min(N-1, 7)$), el cual es un entero no negativo. Amy va primero y se turnan.
En cada turno, el jugador realiza un movimiento siguiendo el procedimiento a continuación:
Elegir un subconjunto $S$ con un número impar de casillas, todas ellas blancas, tal que la distancia entre cualesquiera dos casillas (es decir, la diferencia absoluta de sus coordenadas) en $S$ no exceda $K$.
En particular, siempre es aceptable que $S$ tenga exactamente una casilla blanca, y nunca es posible que $|S|$ exceda $K + 1$ (por supuesto, $|S|$ también debe ser impar).
Colorear todas las casillas en $S$ de rojo o colorear todas ellas de verde, sujeto a la condición de que ninguna casilla roja pueda estar adyacente a una verde. Es posible que este paso sea imposible de completar para algunas elecciones válidas de $S$; en ese caso, el jugador está obligado a elegir $S$ de manera diferente.
El primer jugador que no pueda realizar un movimiento legal pierde.
Dado el estado del tablero antes de que Amy realice su primer movimiento, sin casillas rojas adyacentes a casillas verdes, determine qué jugador ganará si ambos juegan de manera óptima.
Entrada
La entrada consiste en varios casos de prueba. La primera línea contiene un entero $T$ ($1 \le T \le 5 \cdot 10^4$): el número de casos de prueba.
La primera línea de cada caso de prueba contiene $N$ y $K$ ($1 \le N \le 2\cdot 10^5$, $0 \le K \le \min(N-1, 7)$).
La segunda línea de cada caso de prueba contiene una cadena de $N$ caracteres que describe el estado inicial del tablero. Cada carácter es R (rojo), G (verde) o W (blanco). Se garantiza que ninguna R es adyacente a una G.
Se garantiza que la suma de $N$ sobre todos los casos de prueba no excede $4 \cdot 10^5$.
Salida
Para cada caso de prueba, imprima Amy o Aimee, indicando el jugador que ganará.
Puntuación
- ($15$ puntos) $N \le 10$.
- ($15$ puntos) No hay dos casillas blancas adyacentes en el estado inicial.
- ($10$ puntos) El estado inicial es completamente blanco, y $K = 0$.
- ($20$ puntos) $K = 0$.
- ($40$ puntos) Sin restricciones adicionales.
Ejemplos
Entrada 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
Salida 1
Amy Aimee Aimee Amy Amy
Nota
En el primer caso de prueba de ejemplo, Amy puede ganar eligiendo $S$ como todo el tablero y coloreándolo todo de rojo en su primer turno.
En el segundo caso de prueba, Amy no puede realizar un movimiento legal en su primer turno, y pierde inmediatamente.
En el tercer caso de prueba, sin importar lo que Amy haga en su primer movimiento, Aimee siempre es capaz de colorear todo el tablero con el mismo color en su turno, ganando así el juego.