URI Online Judge | 2838

The Infinity Gems

By Diego Rangel, FACIT BR Brazil

Timelimit: 1

The gems of the infinite are a set of six gems that give the bearer domain over some aspect of the universe: Power, Time, Mind, Space, Reality and Soul.

Thanos needs to get all the gems to win back his beloved, Mrs. Death.

In order to prevent the terrible tyrant from getting all the gems, Stephen Strange, the Strange Doctor, built a magical labyrinth and hid inside all 5 gems that are not yet under the control of Thanos and challenged the titan to walk by labyrinth and try to get the gems.

To make the challenge even more interesting, some doors and keys were placed inside the labyrinth . For example, the key a opens any door A, the key b opens any door B, and so on.

Thanos as a good player will not use the powers of the gems until he has all of them, moves one house per second and does not walk diagonally.

Given the labyrinth, determine, if possible, the minimum time spent by Thanos to get all the gems.

Input

The first line contains two integers N and M (N, M ≤ 50) that represent the dimensions of the labyrinth. The next N lines contains M characters that describe the labyrinth, the characters are of type:

Output

You should  print the minimum time if Thanos can get all the gems, or the message "Gamora" without quotes if he can not get the gems.

Input Samples Output Samples

12 12
############
#T.r..a..b.#
####..####A#
#..B.##m...#
#########B##
###t.c.p...#
#########C##
###........#
#d..#......#
#####.##D###
##...D.e.###
############

51

1 12
T..rmteD..p.

Gamora