#include <iostream>
#include <fstream>
#include <string>

#define R 0
#define C 1

using namespace std;

char house[202][22];
int isportal[202][22];
int portalend[11][2];
int portalstartroom[11];
int portalendroom[11];
int interest[5][2];

bool visited[202][22];

void resethouse() {
    for (int r = 0; r < 202; r++) for (int c = 0; c < 22; c++) {
        house[r][c] = '#';
        isportal[r][c] = 0;
    }
    for (int i = 0; i < 11; i++) {
        portalstartroom[i] = portalendroom[i] = 0;
        portalend[i][0] = portalend[i][1] = 0;
    }
    for (int i = 0; i < 5; i++) {
        interest[i][R] = interest[i][C] = 0;
    }
}


bool canreach[202][22][202][22];

int rdiff[] = {1, -1, 0, 0};
int cdiff[] = {0, 0, 1, -1};

void resetvisited() {
    for (int r = 0; r < 202; r++) for (int c = 0; c < 22; c++) {
        visited[r][c] = false;
        for (int r2 = 0; r2 < 202; r2++) for (int c2 = 0; c2 < 22; c2++) canreach[r][c][r2][c2] = false;
    }
}

int rows, cols;


void printhouse() {
    for (int r = 0; r <= rows + 1; r++) {
        for (int c = 0; c <= cols + 1; c++) cout << house[r][c];
        cout << endl;
    }
}

int cangetto(int r1, int c1, int r2, int c2) {
    if (r1 == r2 && c1 == c2 && c2 != '#') {
        canreach[r1][c1][r2][c2] = true;
        return true;
    } else if (canreach[r1][c1][r2][c2]) return true;

    int r, c;

    visited[r1][c1] = true;
    for (int i = 0; i < 4; i++) {
        r = r1 + rdiff[i]; c = c1 + cdiff[i];
        if (house[r][c] != '#' && !visited[r][c]) {
            if (cangetto(r, c, r2, c2)) {
                canreach[r1][c1][r2][c2] = true;
                break;
            }
        }
    }

    if (!canreach[r1][c1][r2][c2]) {
        if (house[r1][c1] >= 'a' && house[r1][c1] <= 'j') {
            int portalnum = house[r][c1] - 'a' + 1;
            r = portalend[portalnum][R]; c = portalend[portalnum][C];
            if (!visited[r][c]) {
                if (cangetto(r, c, r2, c2)) {
                    canreach[r1][c1][r2][c2] = true;
                }
            }
        }
    }

    visited[r1][c1] = false;
    if (canreach[r1][c1][r2][c2]) return true;
    return false;
}

int main() {
    ifstream fin("DATA5.txt");
    ofstream fout("OUT5.txt");
    for (int i = 0; i < 5; i++) {
        resethouse();
        fin >> rows >> cols >> ws;
        string str;
        for (int r = 1; r <= rows; r++) {
            getline(fin, str);
            for (int c = 1; c <= cols; c++) {
                house[r][c] = str[c - 1];
                if (house[r][c] >= 'A' && house[r][c] <= 'J') {
                    int portalnum = house[r][c] - 'A' + 1;
                    portalend[portalnum][R] = r;
                    portalend[portalnum][C] = c;
                    //cout << "Adding portal ending " << portalnum << ": " << r << "," << c << endl;
                }
                if (house[r][c] >= 'a' && house[r][c] <= 'j') {
                    int portalnum = house[r][c] - 'a' + 1;
                    isportal[r][c] = portalnum;
                }
                if (house[r][c] >= '1' && house[r][c] <= '5') {
                    int interestnum = house[r][c] - '1';
                    interest[interestnum][R] = r;
                    interest[interestnum][C] = c;
                    //cout << "Adding POI " << interestnum << ": " << r << "," << c << endl;
                }
            }
        }


        for (int i = 0; i < 5; i++) {
            if (interest[i][C] != 0) {
                fout << (i + 1) << ":";
                for (int j = 0; j < 5; j++) if (j != i && interest[j][C] != 0) {
                    resetvisited();
                    //cout << endl << "Trying " << interest[i][R] << "," << interest[i][C] << "; " << interest[j][R] << "," << interest[j][C] << endl;
                    if (cangetto(interest[i][R], interest[i][C], interest[j][R], interest[j][C])) {
                        fout << (j + 1) << " ";
                    }
                }
                fout << endl;
            }
        }
        // Sanity checks
        //cout << cangetto(2, 5, 4, 10) << endl;

        //printhouse();
    }
}