cho.sh

K-Queen

아직 제출이 없습니다시간 제한1초메모리 제한1024 MB

문제

재헌이는 생일 선물로 크기가 N×NN \times N인 체스판과 백색 킹 하나, 흑색 퀸 100 000100\ 000개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상대 기물을 공격할 수 있다. 기물이 체스판 바깥으로 나갈 수는 없다.

체스판 위에 기물들을 이곳저곳 놓아 보던 재헌이는 다음과 같은 3가지 상태를 발견했다.

  • 체크: 킹이 상대 기물에 의해 공격받고 있으면서, 킹을 한 번 움직여 상대의 공격으로부터 벗어날 수 있는 경우
  • 체크메이트: 킹이 상대 기물에 의해 공격받고 있으면서, 킹을 어떻게 한 번 움직이더라도 상대의 공격으로부터 벗어날 수 없는 경우
  • 스테일메이트: 킹이 공격받고 있지는 않지만, 킹을 어떻게 한 번 움직이더라도 상대 기물에 의해 공격을 받게 되는 경우

아래 그림은 왼쪽부터 각각 체크, 체크메이트, 스테일메이트의 한 가지 예를 보여준다.

신이 난 재헌이는 체스판 위에 백색 킹 하나와 흑색 퀸 KK개를 놓았는데, 이때 백색 킹과 8방향으로 인접한 칸에는 흑색 퀸을 놓지 않았다. 그러고는 이 체스판이 어느 상태에 해당하는지 여러분에게 물어보았다. 재헌이의 질문에 답해보자!

입력

첫째 줄에 체스판의 크기 NN과 흑색 퀸의 수 KK가 주어진다. (3≤N≤109,1≤K≤100 000)(3 \le N \le 10^9, 1 \le K \le 100\ 000)

다음 줄에 백색 킹의 위치 R,CR, C가 주어진다. RR행 CC열에 백색 킹이 있음을 의미한다. (1≤R,C≤N)(1 \le R,C \le N)

다음 KK개의 줄에 걸쳐 각 흑색 퀸의 위치 R_i,C_iR\_i, C\_i가 주어진다. ii번째 퀸이 R_iR\_i행 C_iC\_i열에 있음을 의미한다. (1≤R_i,C_i≤N)(1 \le R\_i, C\_i \le N)

두 기물의 위치가 중복되는 경우는 없으며, 백색 킹과 8방향으로 인접한 칸에 흑색 퀸이 놓여있는 경우는 주어지지 않는다.

출력

주어진 체스판의 상태가 체크이면 CHECK를, 체크메이트이면 CHECKMATE를, 스테일메이트이면 STALEMATE를, 3가지 상태 중 어느 것에도 속하지 않으면 NONE을 출력한다.