Câu lạc bộ MITIT thường xuyên tổ chức các buổi "giao lưu xã hội", là những sự kiện thú vị dành cho các thành viên câu lạc bộ để giao lưu và nghỉ ngơi sau giờ học, viết đề bài hoặc tổ chức cuộc thi. Đồ ăn nhẹ và trò chơi được cung cấp. Nhưng các trò chơi có thể hơi kỳ lạ...
Amy và Aimee, các thành viên của câu lạc bộ MITIT, đang chơi một trò chơi bàn cờ mới mà họ tự sáng tạo ra!
Bàn cờ bao gồm một hàng gồm $N$ ô vuông, mỗi ô được tô màu đỏ, xanh lá cây hoặc trắng. Những người chơi cũng đã thống nhất một tham số $K$ (thỏa mãn $0 \le K \le \min(N-1, 7)$), là một số nguyên không âm. Amy đi trước và họ thay phiên nhau thực hiện lượt chơi.
Trong mỗi lượt, người chơi thực hiện một nước đi theo quy trình dưới đây:
Chọn một tập hợp con $S$ gồm một số lẻ các ô vuông, tất cả đều là màu trắng, sao cho khoảng cách giữa bất kỳ hai ô vuông nào (tức là giá trị tuyệt đối của hiệu tọa độ của chúng) trong $S$ không vượt quá $K$.
Đặc biệt, việc chọn $S$ chỉ có đúng một ô trắng luôn được chấp nhận, và $|S|$ không bao giờ có thể vượt quá $K + 1$ (tất nhiên, $|S|$ cũng phải là số lẻ).
Tô tất cả các ô vuông trong $S$ thành màu đỏ hoặc tô tất cả chúng thành màu xanh lá cây, với điều kiện là không có ô màu đỏ nào được phép nằm cạnh ô màu xanh lá cây. Có khả năng bước này không thể thực hiện được đối với một số lựa chọn $S$ hợp lệ; trong trường hợp đó, người chơi buộc phải chọn $S$ theo cách khác.
Người chơi đầu tiên không thể thực hiện nước đi hợp lệ sẽ thua.
Cho trạng thái của bàn cờ trước khi Amy thực hiện nước đi đầu tiên, với điều kiện không có ô màu đỏ nào nằm cạnh ô màu xanh lá cây, hãy xác định người chơi nào sẽ thắng nếu cả hai đều chơi tối ưu.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 5 \cdot 10^4$): số lượng bộ test.
Mỗi bộ test gồm hai dòng:
- Dòng đầu tiên chứa $N$ và $K$ ($1 \le N \le 2\cdot 10^5$, $0 \le K \le \min(N-1, 7)$).
- Dòng thứ hai chứa một chuỗi gồm $N$ ký tự mô tả trạng thái ban đầu của bàn cờ. Mỗi ký tự là R (đỏ), G (xanh lá cây) hoặc W (trắng). Đảm bảo rằng không có R nào nằm cạnh G.
Tổng $N$ trên tất cả các bộ test không vượt quá $4 \cdot 10^5$.
Dữ liệu ra
Với mỗi bộ test, in ra Amy hoặc Aimee, chỉ ra người chơi sẽ thắng.
Nhiệm vụ con
($15$ điểm) $N \le 10$.
($15$ điểm) Không có hai ô trắng nào nằm cạnh nhau trong trạng thái ban đầu.
($10$ điểm) Trạng thái ban đầu hoàn toàn là màu trắng và $K = 0$.
($20$ điểm) $K = 0$.
($40$ điểm) Không có ràng buộc bổ sung.
Ví dụ
Dữ liệu vào 1
5 5 4 WWWWW 16 3 RRRRWGGGGGWRRRRR 6 5 WWWWWW 12 0 WWWWRRWGGGWW 13 7 WRRWWGWRWRWWW
Dữ liệu ra 1
Amy Aimee Aimee Amy Amy
Ghi chú
Trong bộ test mẫu đầu tiên, Amy có thể thắng bằng cách chọn $S$ là toàn bộ bàn cờ và tô tất cả thành màu đỏ trong lượt đầu tiên của mình.
Trong bộ test thứ hai, Amy không thể thực hiện nước đi hợp lệ trong lượt đầu tiên của mình và cô ấy thua ngay lập tức.
Trong bộ test thứ năm, bất kể Amy làm gì trong nước đi đầu tiên, Aimee luôn có thể tô toàn bộ bàn cờ bằng cùng một màu trong lượt của mình, từ đó thắng trò chơi.