By Emilio Wuerges, UFFS Brazil
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 know 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:
The starting point is always at the top left corner.
The maps are rectangular and each point of the map has one of these symbols:
A traversable terrain space.
An arrow, representing a possible change of direction.
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:
An arrow to the right: >
An arrow to the left: <
An arrow ponting down: v
An arrow pointing up: ^
A space of traversable terrain: .
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|