Description
Writer: jjjjj19980806 Description: pclightyear Photo Credit: eccioa Difficulty: ★★☆☆☆
Fi - Fi - Fi - Fire!!!!!!!!!!!!
eccioa loves playing minecraft, but he is on fire now!
He looks at the mini map, and he wants to found out if there is any water nearby to put out the fire on him. Unfortunately, there is also some lava nearby, and he can't pass through it (he forgot to bring the potion of fire resistance). If he can't reach any of the water on the map, he will be burned to death miserably.
eccioa now gives you the mini map sized m ✕ n consists of four symbols:
'e' stands for the current position of eccioa.
'.' stands for the regular road he can pass through.
'^' stands for lava he cannot pass through.
'~' stands for water. (There may be multiple of them)
Can you tell him whether he can stay alive or not?
Input
The first line contains two integer m, n, representing the size of the map eccioa gives to you.
The next m lines contain n characters, either 'e', '.', '^', '~', representing the status of position aij.
It is guaranteed that :
- 1 ≤ m, n ≤ 1000
Output
If eccioa can stay alive, please print "Alive!", otherwise please print "Dead!".