import java.awt.Point;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.HashMap;
import java.util.Scanner;

import javax.swing.JOptionPane;


public class Question5 {

	static HashMap<Character, Point> points;
	static HashMap<Character, Point> portals;
	static HashMap<Character, Point> portalexits;
	static int width, height;
	static Character[][] tiles;
	static boolean[][] crumbs;
	public static void main(String[] args) throws Exception {
		BufferedWriter fileout = new BufferedWriter(new FileWriter("OUT5.txt"));
		Scanner scan = new Scanner(new FileReader("DATA5.txt"));
		while (scan.hasNextLine()) {
			height = Integer.valueOf(scan.nextLine());
			width = Integer.valueOf(scan.nextLine());
			tiles = new Character[width][height];
			crumbs = new boolean[width][height];
			points = new HashMap<Character, Point>();
			portals = new HashMap<Character, Point>();
			portalexits = new HashMap<Character, Point>();
			for (int y = 0; y < height; y++) {
				String line = scan.nextLine();
				for (int x = 0; x < width; x++) {
					char ch = line.charAt(x);
					if (Character.isDigit(ch)) {
						points.put(ch, new Point(x, y));
						tiles[x][y] = '.';
					} else if (Character.isLetter(ch) && Character.isLowerCase(ch)) {
						portals.put(ch, new Point(x, y));
						tiles[x][y] = ch;
					} else if (Character.isLetter(ch) && Character.isUpperCase(ch)) {
						portalexits.put(ch, new Point(x, y));
						tiles[x][y] = ch;
					} else {
						tiles[x][y] = ch;
					}
				}
			}
			for (int i = 1; i <= 5; i++) {
				fileout.write(i + ":");
				Point start = points.get(String.valueOf(i).charAt(0));
				String pre = "";
				for (int i2 = 1; i2 <= 5; i2++) {
					if (i2 == i) continue;
					look = points.get(String.valueOf(i2).charAt(0));
					if (recurse(start.x, start.y, 0)) {
						fileout.write(pre + i2);
						pre = " ";
					}
				}
				fileout.newLine();
			}
		}
		fileout.close();
	}
	
	static Point look;
	public static boolean recurse(int x, int y, int direction) {
		if (x < 0 || x >= width || y < 0 || y >= height) return false;
		if (tiles[x][y] == '#') {
			return false;
		} else if (x == look.x && y == look.y) {
			return true;
		} else if (crumbs[x][y]) {
			return false;
		}
		Point portal = portals.get(tiles[x][y]);
		if (portal != null) {
			Point exit = portalexits.get(Character.toUpperCase(tiles[x][y]));
			if (exit == null) JOptionPane.showMessageDialog(null, "You suck dwite!");
			boolean temp = recurse(exit.x, exit.y, direction);
			if (temp) return true;
		}
		crumbs[x][y] = true;
		boolean up = false;
		boolean right = false;
		boolean down = false;
		boolean left = false;
		for (int dir = direction; dir < direction + 4; dir++) {
			if ((dir & 3) == 0) {
				up = recurse(x, y - 1, 0);
			} else if ((dir & 3) == 1) {
				right = recurse(x + 1, y, 1);
			} else if ((dir & 3) == 2) {
				down = recurse(x, y + 1, 2);
			} else if ((dir & 3) == 3) {
				left = recurse(x - 1, y, 3);
			}
		}
		crumbs[x][y] = false;
		return up || right || down || left;
	}

}