#include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define Maxn 110

 struct node

 {

     int num,ax[];

 }t[Maxn];

 bool cmp(node x,node y) {return x.num<y.num;} 

 int r,c;

 char s[];

 int w[][],b[][];

 bool vis[Maxn];

 void output()

 {

     for(int i=;i<=r;i++)

      for(int j=;j<=c;j++)

      {

          printf("%d ",t[b[i][j]].num);

          for(int k=;k<;k++)

          {

              int x=t[b[i][j]].ax[(k+w[i][j])%];

              if(x==) printf("0 ");

              else printf("%c ",x+'a'-);

          }

          printf("\n");

      }

 }

 bool ok=;

 void ffind(int x,int y)

 {

     if(x==r+)

     {

         output();

         ok=;

         return;

     }

     if(y==c+) {ffind(x+,);return;}

     for(int i=;i<=r*c;i++) if(!vis[i])

     {

         for(int k=;k<;k++)

           if(t[i].ax[k]==t[b[x-][y]].ax[(w[x-][y]+)%] && t[i].ax[(k+)%]==t[b[x][y-]].ax[(w[x][y-]+)%])

         {

             if(y==c&&t[i].ax[(k+)%]!=) continue;

             if(y!=c&&t[i].ax[(k+)%]==) continue;

             if(x!=r&&t[i].ax[(k+)%]==) continue;

             if(x==r&&t[i].ax[(k+)%]!=) continue;

             w[x][y]=k;

             b[x][y]=i;

             vis[i]=;

             ffind(x,y+);

             vis[i]=;

             if(ok==) return;

         }

     }

 }

 int main()

 {

     scanf("%d%d",&r,&c);

     for(int i=;i<=r*c;i++)

      {

          scanf("%d",&t[i].num);

          for(int k=;k<;k++)

          {

              scanf("%s",s);

              if(s[]=='') t[i].ax[k]=;

              else t[i].ax[k]=s[]-'a'+;

          }

      }

     memset(vis,,sizeof(vis));

     for(int i=;i<;i++) t[].ax[i]=;

     memset(b,,sizeof(b));

     memset(w,,sizeof(w));

     sort(t+,t++r*c,cmp);

     ffind(,);

     return ;

 }