초콜릿 바 게임

시간 제한1초메모리 제한512 MB

요약

루비와 디아가 번갈아 가며 아직 쓰이지 않은 소수 크기의 온전한 정사각형이나 1×1 칸을 먹습니다. 두 사람이 최선을 다할 때 승자를 구합니다.

문제

디아와 루비가 한 변의 길이가 $n \times n$ 인 정사각형 초콜릿 바로 번갈아 가며 게임을 한다. 루비가 먼저 시작한다. 각 차례에 현재 플레이어는 다음 중 하나를 반드시 해야 한다.

이전 라운드에서 어떤 플레이어도 선택하지 않은 소수 $p$ 를 고른다. 그다음 빈 칸(X)을 하나도 포함하지 않는 $p \times p$ 정사각형을 바에서 고르고, 그 안의 초콜릿 칸을 모두 먹는다.
임의의 $1 \times 1$ 초콜릿 칸 하나를 먹는다.

마지막 초콜릿 칸을 먹은 플레이어가 이긴다. 시작할 때 이미 먹혀 있는 칸이 일부 있다. 두 플레이어가 최선을 다하면 누가 이기는가? 참고로 "최선"이란, 어느 플레이어가 상대의 어떤 응수에도 이길 전략을 가지고 있다면 그 전략을 유지하는 수를 둔다는 뜻이다.

첫 줄에 초콜릿 바의 크기를 나타내는 정수 $n$ ( $1 \le n \le 2000$ )이 주어진다. 이어서 $n$ 개의 줄이 주어지며, 각 줄은 $n$ 개의 문자로 이루어진다. 각 문자는 X (빈 칸) 또는 - (초콜릿 칸)이다.

루비가 이기면 RUBY, 디아가 이기면 DIA를 출력한다.