Клуб MITIT регулярно проводит «социальные встречи» — веселые мероприятия, на которых члены клуба могут пообщаться и отдохнуть от учебы, составления задач или организации соревнований. На встречах предоставляются закуски и игры. Но игры бывают немного странными...
Эми и Эйми, члены клуба MITIT, играют в новую настольную игру, которую они сами придумали!
Игровое поле состоит из ряда $N$ клеток, каждая из которых окрашена в красный, зеленый или белый цвет. Игроки также договорились о параметре $K$ ($0 \le K \le \min(N-1, 7)$), который является неотрицательным целым числом. Эми ходит первой, далее игроки ходят по очереди.
В каждый ход игрок выполняет следующие действия:
Выбирает подмножество $S$, состоящее из нечетного количества белых клеток, таких что расстояние между любыми двумя клетками (то есть абсолютная разность их координат) в $S$ не превышает $K$.
В частности, всегда допустимо выбрать $S$, состоящее ровно из одной белой клетки, и $|S|$ никогда не может превышать $K + 1$ (разумеется, $|S|$ также должно быть нечетным).
Перекрашивает все клетки в $S$ в красный цвет или все клетки в $S$ в зеленый цвет, при условии, что никакая красная клетка не может оказаться рядом с зеленой. Возможно, что этот шаг невозможно выполнить для некоторых допустимых выборов $S$; в таком случае игрок обязан выбрать другое $S$.
Игрок, который не может сделать допустимый ход, проигрывает.
Учитывая состояние доски перед первым ходом Эми, при условии, что изначально нет красных клеток, соседствующих с зелеными, определите, кто из игроков победит при оптимальной игре.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Первая строка содержит целое число $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, указав игрока, который победит.
Оценка
- (15 баллов) $N \le 10$.
- (15 баллов) В начальном состоянии нет двух соседних белых клеток.
- (10 баллов) Начальное состояние полностью белое, $K = 0$.
- (20 баллов) $K = 0$.
- (40 баллов) Без дополнительных ограничений.
Примеры
Входные данные 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
Выходные данные 1
Amy Aimee Aimee Amy Amy
Примечание
В первом примере Эми может победить, выбрав $S$ как все поле и перекрасив его в красный цвет на первом же ходу.
Во втором примере Эми не может сделать допустимый ход на первом ходу и сразу проигрывает.
В третьем примере, что бы Эми ни сделала на первом ходу, Эйми всегда может перекрасить все поле в один цвет на своем ходу, тем самым выиграв игру.