Problem E
Robot Riot

A group of high school students have recently been experimenting with robots. They had long feared this day would come, but now their worst nightmare has been realized: the artificial intelligence of the robots has become so advanced that they’ve started to think for themselves, and are of course going to destroy all humanity.

Fortunately there is still hope since the robots are currently inside the school, and it is not known if they can get out. Your task is, given the floor plan of the school and the locations of the robots, determine if any of them can escape, or if they’re all stuck inside.

The floor plan is given as an $n\times m$ matrix consisting of the following characters:

• ‘.’ denoting empty floor space

• ‘#’ denoting a wall or a closed door

• ‘X’ denoting a robot

Robots can drive to adjacent empty floor spaces (but not diagonally).

A robot can escape outside if it can reach the edge of the floor plan.

Input

The first line of input contains two integers $n, m$. Then follow $n$ lines, each containing $m$ characters, describing the floor plan as defined above. You can assume that no robots or walls are on the border of the floor plan.

Output

Output one line containing “Death to humans” if any of the robots can escape, or “We are safe” otherwise.

Grading

Your solution will be graded on a number of subtasks. To get the points for a subtask, you must be accepted on all test cases in the subtask.

8 10
..........
.########.
.#.X....#.
.######.#.
.#..#...#.
....#X..#.
.########.
..........

We are safe

13 13
.............
.###########.
.#.........#.
.#.#######.#.
.#.#.....#.#.
.#.#.###.#.#.
.#.#..X#.#.#.
.#.#####.#.#.
.#.......#.#.
.#########.#.
.#.........#.
.#.#########.
.............

Death to humans

5 5
.....
..#..
.#X#.
..#..
.....

We are safe