28407번 - 그건 가지가 아니라 대파예요

어버진과 스칼리온이 $N$행 $M$열 격자 모양 게임판에서 게임을 한다. 격자의 각 칸에는 ‘가’, ‘지’, ‘대’, ‘파’, ‘☆’ 중 하나가 적혀있다.

이 게임에서는 스칼리온과 어버진이 번갈아 자기 턴을 수행한다. 스칼리온이 먼저 턴을 수행한다.

스칼리온은 자신의 차례에서 왼쪽 칸이 ‘가’이고 오른쪽 칸이 ‘지’인 가로 방향으로 인접한 두 타일을 선택하여 해당 두 칸을 ‘대‘, ‘파’로 바꿀 수 있다. 어버진은 자신의 차례에서 위쪽 칸이 ‘대’이고 아래쪽 칸이 ‘파’인 세로 방향으로 인접한 두 타일을 선택하여 해당 두 칸을 ‘가’, ‘지’로 바꿀 수 있다.

어버진과 스칼리온 모두 타일을 바꾸는 방법이 있다면 반드시 타일을 바꿔야 한다. 게임을 진행하다가 자기 턴을 수행할 수 없는 쪽은 지게 된다. 만약 $10^{100}$턴이 지난 이후에도 게임이 끝나지 않는다면 게임이 무승부로 종료된다.

어버진과 스칼리온은 각자 최선을 다하여 게임을 플레이한다. 즉, 두 플레이어는 이기는 방법이 있으면 이기는 수를 선택하며 이기는 방법이 없지만 비기는 방법이 있으면 비기는 수를 선택한다.

게임판이 주어지면 게임의 승자를 구하는 프로그램을 작성하여라.

첫 번째 줄에 게임판의 크기 $N,M$ $(2\le N,M\le 2\, 500)$ 이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 각 격자의 내용이 알파벳 대문자로 공백 없이 주어진다. G는 ‘가’, Z는 ‘지’, D는 ‘대’, P는 ‘파’, X는 ‘☆’에 대응된다.

어버진과 스칼리온이 최선을 다하여 게임을 했을 때 어버진이 이긴다면 Aubergine을, 스칼리온이 이긴다면 Scallion을, 무승부라면 Draw를 출력한다.