랭크 앤 파일 (체스 체크·체크메이트 판정)

체스를 두는 프로그램은 컴퓨터의 역사만큼이나 오래되었고, 1997년에는 IBM의 딥 블루가 세계 챔피언 게리 카스파로프를 이겼습니다. 이런 프로그램은 모두 승부가 결정되는 국면, 즉 체크메이트를 알아볼 수 있어야 합니다. 체스판의 현재 배치가 주어질 때, 이번에 둘 차례인 쪽의 킹이 안전한지(safe), 체크(check) 상태인지, 체크메이트(checkmate) 상태인지 판정하세요.

체스는 $8 \times 8$ 칸의 판 위에서 진행됩니다. 여기서 칸의 색은 의미가 없으며, 판 전체를 균일한 격자로 다룹니다.

백과 흑, 두 진영이 겨룹니다. 이 문제에서 각 진영은 다섯 종류의 기물만 사용합니다 — 킹, 퀸, 룩, 비숍, 나이트 (폰은 없습니다). 두 진영은 한 턴에 정확히 기물 하나씩 번갈아 움직이며, 어느 쪽도 자기 차례를 건너뛸 수 없습니다.

각 기물의 이동 규칙은 다음과 같습니다.

• 룩(Rook): 가로줄 또는 세로줄을 따라(상하좌우 네 방향) 직선으로 원하는 만큼 칸을 이동합니다.
• 비숍(Bishop): 대각선(네 대각 방향)을 따라 직선으로 원하는 만큼 칸을 이동합니다.
• 퀸(Queen): 상하좌우와 대각선을 포함한 여덟 방향 중 하나를 따라 직선으로 원하는 만큼 칸을 이동합니다.
• 나이트(Knight): 한 방향으로 두 칸, 그에 수직인 방향으로 한 칸 "뛰어" 이동하며, 목적지 후보는 최대 여덟 칸입니다. 나이트는 사이에 있는 다른 기물에 막히지 않습니다.
• 킹(King): 여덟 방향 중 하나로 한 칸만(바로 인접한 칸으로) 이동합니다.

기물은 빈 칸으로 이동하거나, 상대 기물이 있는 칸으로 이동해 그 기물을 잡아 판에서 제거할 수 있습니다. 아군 기물이 있는 칸으로는 이동할 수 없습니다. 나이트를 제외한 모든 기물은 칸을 따라 "미끄러지듯" 이동하므로, 이동 경로에 놓인 기물은 아군이든 적군이든 그 방향으로의 이후 이동을 모두 막습니다.

킹은 직접 잡히지는 않지만 위협받을 수 있습니다. 상대 기물이 다음 수에 킹을 잡을 수 있는 상태를 체크(check)라고 합니다. 체크를 당한 쪽은 킹을 안전한 곳으로 옮기거나, 다른 기물로 위협을 막거나, 위협하는 기물을 잡아서 대응해야 하며, 어느 쪽도 자기 킹을 체크 상태에 두는 수는 둘 수 없습니다. 둘 차례인 쪽이 체크 상태인데 그 체크를 벗어나게 하는 합법적인 수가 하나도 없으면 체크메이트(checkmate)이며, 그 쪽이 패배합니다.

캐슬링이나 앙파상 같은 다른 체스 규칙은 적용하지 않습니다. 각 판에는 백 킹과 흑 킹이 정확히 하나씩 있으며, 룩·비숍·퀸·나이트는 각 진영이 몇 개든 가질 수 있습니다.

첫 줄에는 데이터 집합의 개수를 나타내는 정수 $D$ ($1 \le D \le 100$)가 주어집니다. 각 데이터 집합은 다음으로 이루어집니다.

• 분석할 쪽, 즉 이번에 둘 차례인 쪽을 나타내는 한 글자가 담긴 줄. 소문자 w는 백, 대문자 B는 흑을 뜻합니다.
• 판을 위에서 아래로 나타내는, 각각 여덟 글자로 된 여덟 줄. 각 글자는 다음 중 하나입니다.
  • . — 빈 칸
  • 소문자 r, b, q, n, k — 백의 룩, 비숍, 퀸, 나이트, 킹
  • 대문자 R, B, Q, N, K — 흑의 같은 기물들

각 데이터 집합마다 한 줄을 출력합니다. 분석한 쪽에 따라 WHITE IS 또는 BLACK IS 로 시작하고, 그 쪽 킹이 체크 상태이면 CHECKED, 체크메이트 상태이면 CHECKMATED, 둘 다 아니면 SAFE를 이어 붙입니다.

위에 설명한 다섯 종류의 기물과 이동 규칙만 사용합니다. 폰이나 특수 규칙은 없습니다. 각 칸의 색은 판정과 무관하며, 분석 대상은 항상 이번에 둘 차례인 쪽입니다.