Description
One day, you find out that you are trapped in a maze. While panicking, you see a mini map in front of you.
Unfortunately, you are still not sure if you can escape from this maze or not, and so, what you need to do is to determine whether you can reach the destination of this maze or not !
You can only move left, right, up, and down (diagonal move is not acceptable) !
The mini map is a size m x n matrix, and it consists of four symbols:
'.' is the road you can walk through.
'x' is the wall that you can not walk through.
'S' is the the starting point.
'D' is the destination you want to reach.
Your goal is to find whether there exists a path from the starting point S to destination D.
For example, a 4 x 5 map will look like:
D . . . .
x x x x .
x x x x .
S . . . .
(There is a space in front of each charactor!)
Input
There will be 3 parts of input.
(1) The first line contains two integers m, n, which is length and width of the map (1 ≤ m, n ≤ 1000)
(2) The second line is a positive integer T, which is the number of testcases.
(3) There areT amounts of m*n mini map separated by a newline character among each mini map, which contains characters including '.', 'x', 'S', 'D' .
Output
If you can reach the destination, please print "ESCAPE!", otherwise print "QQ".
Note that you need to print a newline character ('\n') at the end.