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

#define NAME "starry"
/* MAXSTAR is the largest a cluster can be */
#define MAXSTAR 160

/* the board */
char board[100][100];
int w, h;

/* clusters already lettered */
int stars[26][MAXSTAR]; /* stars are stored as xval + yval*1000 */
int count[26]; /* number of stars */
int size[26][2]; /* the x & y dimensions */
int nstart; /* number of clusters */

/* the current cluster */
int current[MAXSTAR][2]; /* y, x */
int ncurrent; /* number of stars in current cluster */

/* int_comp is integer comparison, used for bsearch and qsort */
int
int_comp(const void *pa, const void *pb)
 {
  int a = *(int*)pa;
  int b = *(int*)pb;
  if (a > b) return 1;
  else if (a < b) return -1;
  else return 0;
 }

/* find the boundary (in my,mx,My, and Mx.. m is minimum, M is maximum */
/* also fills in current */
int
find_boundary(int y, int x, int *my, int *mx, int *My, int *Mx)
 {
  int rv = 0;
  if (board[y][x] != '1') return 0; /* not a star or already visited */
  rv++; /* one more star */
  board[y][x] = '2'; /* mark as visited */

  /* put in current cluster */
  current[ncurrent][0] = y;
  current[ncurrent][1] = x;
  ncurrent++;

  /* update boundary */
  if (y < *my) *my = y;
  if (y > *My) *My = y;
  if (x < *mx) *mx = x;
  if (x > *Mx) *Mx = x;

  /* check all adjacent stars */
  if (x > 0) 
   {
    x--;
    rv += find_boundary(y, x, my, mx, My, Mx);
    if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
    if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
    x++;
   }
  if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
  if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
  if (x+1 < w)
   {
    x++;
    rv += find_boundary(y, x, my, mx, My, Mx);
    if (y > 0) rv += find_boundary(y-1, x, my, mx, My, Mx);
    if (y+1 < h) rv += find_boundary(y+1, x, my, mx, My, Mx);
    x--;
   }
  return rv;
 }

/* this is a very basic flood fill...fill ch everywhere there's not a '0' */
void
mark_shape(int y, int x, char ch)
 {
  if (board[y][x] == ch) return; /* done already */
  if (board[y][x] == '0') return; /* nothing to do */

  board[y][x] = ch;

  /* recurse on all boundary stars */
  if (x > 0) 
   {
    x--;
    mark_shape(y, x, ch);
    if (y > 0) mark_shape(y-1, x, ch);
    if (y+1 < h) mark_shape(y+1, x, ch);
    x++;
   }
  if (y > 0) mark_shape(y-1, x, ch);
  if (y+1 < h) mark_shape(y+1, x, ch);
  if (x+1 < w) 
   {
    x++;
    mark_shape(y, x, ch);
    if (y > 0) mark_shape(y-1, x, ch);
    if (y+1 < h) mark_shape(y+1, x, ch);
   }
 }

/* is shape id the same as the current shape */
/* specify the orientation with dy/dx and by/bx */
/* dy/dx is the difference value to associate with y and x changes */
/* by/bx is the upper right corner of the bounding box with respect
   to the current orientation */
/* NOTE: assumes that the number of stars are the same */
int
check_shape(int id, int dy, int dx, int by, int bx)
 {
  int lv;
  int pval;

  for (lv = 0; lv < ncurrent; lv++)
   {
    pval = (current[lv][0]-by)*dy + (current[lv][1]-bx)*dx;
    if (!bsearch(&pval, stars[id], count[id], sizeof(stars[id][0]), int_comp))
      return 0; /* found a star that didn't match */
   }
  return 1;
 }

/* we found a star here, make it a cluster */
void
fix_board(int y, int x)
 {
  int mx, my, Mx, My;
  int cnt;
  int lv;
  int pw, ph;
  int f;

/* gather the cluster information */
  mx = Mx = x;
  my = My = y;

  ncurrent = 0;
  cnt = find_boundary(y, x, &my, &mx, &My, &Mx);

  pw = Mx - mx + 1;
  ph = My - my + 1;

  f = 0;
  /* check each cluster */
  for (lv = 0; lv < nstart; lv++)
    if (cnt == count[lv]) /* the cluster must have the same # of stars */
     {
      if (pw == size[lv][1] && ph == size[lv][0])
       { /* the bounding box sizes match */
	f += check_shape(lv, 1000, 1, my, mx);
	f += check_shape(lv, 1000, -1, my, Mx);
	f += check_shape(lv, -1000, 1, My, mx);
	f += check_shape(lv, -1000, -1, My, Mx);
       }
      if (pw == size[lv][0] && ph == size[lv][1])
       { /* the bounding box sizes match */
	f += check_shape(lv, 1, 1000, my, mx);
	f += check_shape(lv, 1, -1000, my, Mx);
	f += check_shape(lv, -1, 1000, My, mx);
	f += check_shape(lv, -1, -1000, My, Mx);
       }
      if (f) break;
     }
  if (f) mark_shape(y, x, 'a' + lv); /* found match */
  else { /* new cluster! */
    count[nstart] = 0;
    mark_shape(y, x, 'a' + nstart);
    for (lv = 0; lv < ncurrent; lv++)
      stars[nstart][lv] = (current[lv][0]-my)*1000 + (current[lv][1]-mx);
    count[nstart] = ncurrent;
    /* we need the stars in increasing order */
    qsort(stars[nstart], count[nstart], sizeof(stars[nstart][0]), int_comp);
    size[nstart][0] = ph;
    size[nstart][1] = pw;
    nstart++;
   }
 }


int
main(int argc, char **argv)
 {
  FILE *fin, *fout;
  int lv, lv2;

  fin = stdin;
  fout = stdout;
  assert(fin);
  assert(fout);

/* read in the data */
  fscanf (fin, "%d %d", &w, &h);

  for (lv = 0; lv < h; lv++) fscanf (fin, "%s", board[lv]);
  fclose(fin);

/* everywhere there's a star not in a cluster, make it into one */
  for (lv = 0; lv < h; lv++)
    for (lv2 = 0; lv2 < w; lv2++)
      if (board[lv][lv2] == '1')
        fix_board(lv, lv2);

/* output data */
  for (lv = 0; lv < h; lv++)
   {
    fprintf (fout, "%c", board[lv][0]);
    for (lv2 = 1; lv2 < w; lv2++)
      fprintf (fout, "%c", board[lv][lv2]);
    fprintf (fout, "\n");
   }

  fclose(fout);
  return 0;
 }