beecrowd | 1855

Maester's Map

By Emilio Wuerges, UFFS Brazil

Timelimit: 1

Sam found a big bunch of maps from old Maester Aemon, which at a first look, should point, each one, a location of a chest full of obsidian. However, after taking a better look, some maps had obvious errors, while others, only sending a team of explorers to know.

What is known is that some maps point to an absurd location outside of the map and some end up in circles, ending up to be completely useless.

Since the maps are many, the brothers of the Nights Watch are few and winter is comming, your work is to write a program to check if a map leads or not to a chest with obsidian.

Maps have these features:

Since the places these maps describe are very dangerous, it is vital that the path described in the map is strictly followed.


The first line contains a positive integer x < 100 with the width of the map.

The second line contains a positive integer y < 100 with the height of the map.

The following lines contain various characters within the map's dimensions.
The valid characters are:


The output must consist of a single line containing a single character ! or *.

! means that the map is invalid. * means that the map is valid.

Input Samples Output Samples