26006번 - K-Queen

문제

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

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

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

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

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

입력

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

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

다음 $K$개의 줄에 걸쳐 각 흑색 퀸의 위치 $R_i, C_i$가 주어진다. $i$번째 퀸이 $R_i$행 $C_i$열에 있음을 의미한다. $(1 \le R_i, C_i \le N)$

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

출력

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

제한

힌트