Scallion, Not Eggplant

Time limit2sMemory limit1024 MB

Summary

Given a grid of 가, 지, 대, 파, and ☆ tiles, decide whether Scallion, Aubergine, or neither wins the alternating move game under optimal play.

Level: Hard8 of 10
Topics: Game theory, Graph, Matrix
Solved: No attempts yet

Problem

Aubergine and Scallion play a game on a grid board with $N$ rows and $M$ columns. Each cell contains one of ‘가’, ‘지’, ‘대’, ‘파’, or ‘☆’.

Scallion and Aubergine take turns, and Scallion moves first.

On his turn, Scallion picks two horizontally adjacent cells where the left cell is ‘가’ and the right cell is ‘지’, and changes them to ‘대’ and ‘파’. On her turn, Aubergine picks two vertically adjacent cells where the top cell is ‘대’ and the bottom cell is ‘파’, and changes them to ‘가’ and ‘지’.

If a player can change a pair of tiles, that player must make a change. A player who cannot make a turn loses. If the game is still running after $10^{100}$ turns, the game ends in a draw.

Both players play as well as they can. If a player can win, that player makes a winning move. If there is no winning move but a drawing move exists, that player makes a drawing move.

Given the board, find the winner of the game.

Input

The first line contains the board size $N$ and $M$ $(2\le N,M\le 2\,500)$ , separated by a space. The next $N$ lines contain the rows of the board as uppercase letters with no spaces. G stands for ‘가’, Z for ‘지’, D for ‘대’, P for ‘파’, and X for ‘☆’.

Output

If Aubergine wins with both players playing optimally, print Aubergine. If Scallion wins, print Scallion. If the game is a draw, print Draw.

Examples2

Example 1
Input
```
3 3
GZX
PXG
XGZ
```
Expected output
```
Scallion
```
Example 2
Input
```
2 2
GZ
PD
```
Expected output
```
Aubergine
```