Description

2 3 
1 c d 0 0
2 0 d b 0
3 c 0 d a
4 b a b 0
5 d 0 0 e
6 0 0 b e

1 0 c d 0
3 0 d a c
5 0 0 e d
2 d b 0 0
4 a b 0 b
6 e 0 0 b

Hint

#include<bits/stdc++.h>
using namespace std;
const int N=15, M=150;
struct node{
	int id, e[5];
} a[M]; // 0上 1右 2下 3左
int n, m, S, w[N][N], b[N][N]; bool v[M];
bool cmp(node n1, node n2){
	return n1.id<n2.id;
}
int calc(int x, int y){
	return (x-1)*m+y;
}
bool jd1(int x, int y, int i, int j){
	int t1=w[x-1][y], t2=w[x][y-1];
	if(a[i].e[j]!=a[b[x-1][y]].e[(w[x-1][y]+2)%4] && x>1) return 0; 
	if(a[i].e[(j+3)%4]!=a[b[x][y-1]].e[(w[x][y-1]+1)%4] && y>1) return 0; 
	return 1;
}
bool jd2(int x, int y, int i, int j){
	if(x!=1 && a[i].e[j%4]==0) return 0; 
	if(x==1 && a[i].e[j%4]!=0) return 0; 
	if(y==1 && a[i].e[(j+3)%4]!=0) return 0; 
	if(y!=1 && a[i].e[(j+3)%4]==0) return 0; 
	if(x!=n && a[i].e[(j+2)%4]==0) return 0; 
	if(x==n && a[i].e[(j+2)%4]!=0) return 0; 	
	if(y==m && a[i].e[(j+1)%4]!=0) return 0; 
	if(y!=m && a[i].e[(j+1)%4]==0) return 0; 
	return 1;
}
bool dfs(int x, int y){
	if(y>m){
		return dfs(x+1, 1);
	}
	if(x>n){
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++){
				printf("%d ", a[b[i][j]].id);
				for(int k=0; k<4; k++){
					int d=a[b[i][j]].e[(k+w[i][j])%4];
					if(d==0) printf("0 ");
					else printf("%c ", d+'a'-1);
				}
				printf("\n");
			}
		return 1;
	}
	for(int i=1; i<=S; i++) if(!v[i]){
		for(int j=0; j<4; j++){
			if(jd1(x, y, i, j) && jd2(x, y, i, j)){
				w[x][y]=j; b[x][y]=i; v[i]=1;
				if(dfs(x, y+1)) return 1;
				w[x][y]=0; b[x][y]=0; v[i]=0;
			}
		}
	}
	return 0;
}
int main(){
	scanf("%d%d", &n, &m); S=n*m;
	for(int i=1; i<=S; i++){
		char s[5]; scanf("%d", &a[i].id);
		for(int j=0; j<4; j++){
			scanf("%s", s);
			if(s[0]=='0') a[i].e[j]=0;
			else a[i].e[j]=s[0]-'a'+1;
		}
	}
	memset(v, 0, sizeof(v));
	memset(w, 0, sizeof(w));
	memset(b, 0, sizeof(b));
	sort(a+1, a+S+1, cmp);;
	bool flag=dfs(1, 1);
	return 0;
}