/*

Starry Night (IOI 1998)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Il problema non richiede conoscenze profonde per essere risolto, ma e` di
grande complicazione algoritmica. Gli off-by-one non si contano. Ci sono
dozzine di dettagli che e` molto difficile mettere a punto.

Inoltre, non e` banale trovare la strada giusta tra una soluzione
algoritmicamente elegante ed efficiente, ma di implementazione laboriosa, e
un'implementazione veloce da realizzare ma troppo lenta in esecuzione.

In una prima fase il file di input viene scandito e inserito nella matrice p;
con un semplice algoritmo di esplorazione in profondita` la costellazione
i viene colorata con -i-1. Le celle vuote di p sono colorate con 0. Di ogni
costellazione vengono memorizzate le dimensioni, il punto inferiore sinistro
e superiore destro del rettangolo minimo che la contiene e le coordinate del
primo punto incontrato durante la scansione.

In una seconda fase la matrice p viene scandita nuovamente. Ora ogni
costellazione incontrata viene confrontata con i tipi noti. Se e` nuova il
suo indice viene memorizzato nel vettore ind. Altrimenti viene ricolorata con
la lettera opportuna. Si noti che la _prima_ costellazione incontrata in una
classe non viene immediatamente ricolorata. La ragione sta nella funzione
copiacost(), che copia in maniera piuttosto rozza una costellazione in una
matrice temporanea, e per fare cio` identifica la costellazione tramite il
suo colore. Se accanto alla prima costellazione di un certo tipo ce ne fosse
un'altra simile, copiacost() copierebbe anche i pezzi della seconda
costellazione contenuti nel rettangolo minimo che contiene la prima.

*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>

#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))

#define MAXDIM 100       /* Massima ampiezza/altezza */
#define MAXCOST 500      /* Massimo numero di costellazioni */
#define MAXCOSTDIV 26    /* Massimo numero di costellazioni _diverse_ */
#define MAXSTELLE 160    /* Massimo numero di stelle per costellazione */

int p[MAXDIM][MAXDIM];  /* Punti del cielo */
char T[MAXDIM][MAXDIM], U[MAXDIM][MAXDIM];
								/* Matrici temporanee per memorizzare costellazioni */
int W, H;

/* Queste variabili individuano un punto della costellazione (il primo
incontrato), il rettangolo minimo che contiene la costellazione e le sue
dimensioni (larghezza e altezza). */
int x[MAXCOST], y[MAXCOST], minX[MAXCOST], minY[MAXCOST],
	maxX[MAXCOST], maxY[MAXCOST], l[MAXCOST], a[MAXCOST];

int ind[MAXCOSTDIV]; /* Indice della prima costellazione nella classe
								di similitudine. */


/* Questa funzione scandisce una costellazione a partire dal punto x,y. La
costellazione viene colorata con colore -cost-1 (cost e` l'indice della
costellazione). Il meccanismo utilizzato e` una semplice scansione in
profondita`. Mano a mano che la costellazione viene esplorata le variabili
maxX, minX, maxY e minY vengono aggiornate. */

int scandisci(int x, int y, int cost) {

	int i,j;

	if (p[x][y] != 1) return;

	minX[cost] = min(minX[cost], x);
	maxX[cost] = max(maxX[cost], x);
	minY[cost] = min(minY[cost], y);
	maxY[cost] = max(maxY[cost], y);
	p[x][y] = -cost-1;

	for(i=-1; i<=1; i++) for(j=-1; j<=1; j++)
		if ((i || j) && x+i>=0 && x+i<W && y+j>=0 && y+j<H) scandisci(x+i, y+j, cost);

}


/* Questa funzione ricolora la costellazione cost (che si suppone colorata
	con il colore -cost-1) con il colore m partendo da un punto x,y della
	costellazione stessa. Anche in questo caso utilizziamo una scansione in
	profondita`. */

int ricolora(int x, int y, int cost, int m) {

	int i,j;

	if (p[x][y] != -cost-1) return;

	p[x][y] = m;

	for(i=-1; i<=1; i++) for(j=-1; j<=1; j++)
		if ((i || j) && x+i>=0 && x+i<W && y+j>=0 && y+j<H) ricolora(x+i, y+j, cost, m);

}


/* Questa funzione copia il la costellazione di indice cost, colorata da
-cost-1, nella matrice M. Per fare cio` scandisce il rettangolo minimo che
contiene la costellazione e controlla quali caselle hanno colore -cost-1.
Perche' questa funzione sia corretta occorre che la costellazione copiata
abbia un colore non condiviso da nessun'altra costellazione! */

int copiacost(int cost, int M[MAXDIM][MAXDIM]) {
	int i,j;

	for(i=0; i<l[cost]; i++)
		for(j=0; j<a[cost]; j++)
			M[i][j] = (p[minX[cost]+i][minY[cost]+j] == -cost-1);
}



/* Questa funzione controlla se due costellazioni contenute nelle matrici A e
B (normalizzate in modo che la prima colonna e la prima riga di entrambe le
matrici contengano almeno un punto della costellazione) sono simili. Per fare
cio` richiede la larghezza e l'altezza della prima costellazione, e una
coppia <valore di partenza, incremento> per l'ascissa e l'ordinata della
seconda costellazione. Passando incrementi positivi o negativi e` possibile
"ribaltare" la seconda costellazione. Infine, se l'ultima variabile e`
nonzero il test viene effettuato _scambiando le coordinate x e y della
seconda costellazione_. In questo modo simuliamo un ribaltamento lungo la
diagonale. */

int simili(int A[MAXDIM][MAXDIM], int B[MAXDIM][MAXDIM],
					int l, int a, int startx, int incrx, int starty, int incry,
					int invertixy) {

	int i, j;

	for(i=0; i<l; i++)
		for(j=0; j<a; j++) {
			if (invertixy) {
				if (A[i][j] != B[starty + j*incry][startx + i*incrx]) return 0;
			}
			else if (A[i][j] != B[startx + i*incrx][starty + j*incry]) return 0;
		}

	return 1;
}





int main(int argc, char *argv[]) {

	char c;
	int i, j, k, ncost, nclassi=0;

	scanf("%d\n%d\n", &W, &H);

	for(j=0; j<H; j++) {
		for(i=0; i<W; i++) {
			scanf("%c", &c);
			p[i][j]= c-'0'; /* Leggiamo l'input e lo convertiamo in 0/1 */
		}
		scanf("\n");
	}

	/* Prima fase: scandiamo una per una le costellazioni
		e assegnamo x, y, l e a. */

	for(i=0; i<MAXCOST; i++)
		minX[i] = minY[i] = INT_MAX; /* I minimi sono inizializzati a infinito. */

	for(ncost=j=0; j<H; j++)
		for(i=0; i<W; i++)
			if (p[i][j] == 1) {
				x[ncost] = i;
				y[ncost] = j;
				scandisci(i, j, ncost);
				l[ncost] = maxX[ncost]-minX[ncost]+1;
				a[ncost] = maxY[ncost]-minY[ncost]+1;
				ncost++;
			}

	/* Seconda fase: scandiamo nuovamente le costellazioni. */

	for(i=0; i<ncost; i++) {
		copiacost(i, T); /* T ora contiene la costellazione di indice i. */

		for(j=0; j<nclassi; j++) {
			copiacost(ind[j], U);	/* Esaminiamo il j-esimo tipo di
						costellazione copiando la costellazione ind[j] in U. */

			/* Ci sono otto possibili combinazioni di incrementi lungo l'ascissa
			e l'ordinata e di inversione delle coordinate. Chiaramente dobbiamo
			prima controllare che ampiezza e altezza coincidano. */

			if (l[ind[j]] == l[i] && a[ind[j]] == a[i]
				 && (simili(T, U, l[i], a[i], 0, 1, 0, 1, 0)
					  || simili(T, U, l[i], a[i], 0, 1, a[i]-1, -1, 0)
					  || simili(T, U, l[i], a[i], l[i]-1, -1, 0, 1, 0)
					  || simili(T, U, l[i], a[i], l[i]-1, -1, a[i]-1, -1, 0))

				 || l[ind[j]] == a[i] && a[ind[j]] == l[i]
				 && (simili(T, U, l[i], a[i], 0, 1, 0, 1, 1)
					  || simili(T, U, l[i], a[i], 0, 1, a[i]-1, -1, 1)
					  || simili(T, U, l[i], a[i], l[i]-1, -1, 0, 1, 1)
					  || simili(T, U, l[i], a[i], l[i]-1, -1, a[i]-1, -1, 1))) {

				ricolora(x[i], y[i], i, j+'a');

				break;
			}
		}

		/* Se la costellazione corrente non e` classificabile, creiamo un
			nuovo tipo. */

		if (j == nclassi) ind[nclassi++] = i;
	}

	/* Infine, ricoloriamo i rappresentanti di ogni classe. */

	for(i=0; i<nclassi; i++) ricolora(x[ind[i]], y[ind[i]], ind[i], i+'a');

	for(i=0; i<H; i++) {
		for(j=0; j<W; j++) printf("%c", p[j][i] ? p[j][i] : '0');
		printf("\n");
	}
}