The input consists of several maps. Each map begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 100) specifying the map size. Then there are R lines each containing C characters. Each character is one of the following:
Note that it is allowed to have more than one exit, no exit at all, more doors and/or keys of the same color, and keys without corresponding doors and vice versa.
You may assume that the marker of your position (“*”) will appear exactly once in every map.
There is one blank line after each map. The input is terminated by two zeros in place of the map size.