GPS for Autonomous Driving — Max 2 Turns

In a grid with obstacles, determine whether there is a path from Q to W with at most two turns. The vehicle can only move up, down, left or right; each change of moving direction counts as one turn.

This site's input format and constraints are given below.

输入格式

The first line contains b p, followed by b lines of p characters each (separated by spaces): o is open ground, x is an obstacle, Q is the start and W is the destination. This site's ranges: 1≤b,p≤1000; Q/W each appear exactly once.

输出格式

Output DRIVE! if W is reachable, otherwise output DON'T DRIVE!.

样例 1

输入：

4 4
Q o o o
o o o o
o o o o
o o o W

输出：

DRIVE!

样例 2

输入：

3 5
Q x o o W
x x x x x
o o o o o

输出：

DON'T DRIVE!

样例 3

输入：

3 3
Q o o
x x o
W o o

输出：

DRIVE!