#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;

typedef struct {
	vector<int> edges[405];
	int degrees[405];
	char grid[20][20];
	int nv;
}graph;


bool visit[5];
int points[5];

void bfs(graph* g, int start) {
	queue<int> nodes;
	bool visited[404];
	for (int i=0; i<404; i++) visited[i] = false;
	visited[start]= true;
	
	nodes.push(start);
	
	while(!nodes.empty()) {
		int v = nodes.front(); nodes.pop();
		//cout << v << endl;
		for (int i=0; i<5; i++) if (points[i] == v) visit[i] = true;
		
			for (int i=0; i< g->edges[v].size(); i++) {
				int u = g->edges[v][i]; //cout << u << " ";
				if (!visited[u]) {
					visited[u] = true;
					nodes.push(u);
				}
			}
	}

}

int main() {
    ifstream fin("data5.txt");
	ofstream fout("out5.txt");
	
	for (int ncases=0; ncases<5; ncases++) {
		graph* g = new graph;
		
		//input grid
		int m, n; fin >> m >> n;	//first down, then right
		
		g->nv = m*n;
		
		int portals[10][2];
		bool bPortal[10];
		for (int i=0; i<10; i++) bPortal[i] = false;
		
		for (int i=0; i<m; i++)
			for(int j=0; j<n; j++) {
				fin >> g->grid[i][j];
				if ( 'a' <= g->grid[i][j] && g->grid[i][j]<= 'j' ) {
					portals[g->grid[i][j] - 'a'][0] = i*n+j;
					bPortal[g->grid[i][j] - 'a'] = true;
                }
				if ( 'A' <= g->grid[i][j] && g->grid[i][j] <= 'J' )
					portals[g->grid[i][j] - 'A'][1] = i*n+j;
				if ( '1' <= g->grid[i][j] && g->grid[i][j] <='5' )
					points[g->grid[i][j] - '1'] = i*n+j;
			}
			
		//convert to graph
		for (int i=0; i<m; i++)
			for(int j=0; j<n; j++) {
				if(g->grid[i][j] == '#') continue;
				int index = i*n + j;
				if ( i > 0 && g->grid[i-1][j] != '#')
					g->edges[index].push_back(index-n);
				if ( i < m-1 && g->grid[i+1][j] != '#')
					g->edges[index].push_back(index+n);
				if ( j > 0 && g->grid[i][j-1] != '#')
					g->edges[index].push_back(index-1);
				if ( j < n-1 && g->grid[i][j+1] != '#') 
					g->edges[index].push_back(index+1);
				for (int k = 0; k<10; k++) {
                    if (!bPortal[k]) continue;
					if (portals[k][0] == index)
						g->edges[index].push_back(portals[k][1]);
               }
            }
		// system("pause");
		//run bfs from each one of the points
		for (int i=0; i<5; i++) { 
            for (int j = 0; j<5; j++) visit[j] = false;
			bfs(g, points[i]);
			
			//ouput
			fout << i+1 << ":";
			bool first = true;
			for (int j = 0; j<5; j++) {
				if (j==i) continue;
				if (visit[j] && first) {
					first = false;
					fout << j+1;
                }
				else if (visit[j])
					fout << " " << j+1;
			}
			fout << endl;
		}
	}
	
	
    return 0;
}