rendered paste body#include <iostream>
#include <sstream>
#include <vector>
#include <stack>
using namespace std;
class piece{
public:
vector<string> vs;
int top,left,bottom,right;
};
void recur(vector<vector<int> > vi,piece puzzle[], bool used[],int size,int x,int y){
for(int i=0;i<size;i++){
if(used[i]==false){
used[i]=true;
//check boundary
if(x+1<vi.size()){
//recur
if(vi[x+1][y]==-1){
if(puzzle[i].left ==(puzzle[vi[x][y]].right*-1)){
vi[x+1][y]=i;
recur(vi,puzzle,used,size,x+1,y);
}
}
}else{
x=0;
if(y+1<vi.size()){
if(vi[x][y+1]==-1){
y++;
if(puzzle[i].top ==(puzzle[vi[x][y]].bottom*-1)){
vi[x][y+1]=i;
recur(vi,puzzle,used,size,x,y+1);
}
}
//recur
}else{
break;
}
}
}
}
//check all used and output if necessary
bool flag=true;
for(int i=0;i<size;i++){
if(used[i]==false){
flag=false;
// cout<<"cant be done";
}
}
if(flag==true){
for(int i=0;i<vi.size();i++){
for(int j=0;j<vi[i].size();j++){
// for(int k=0;k<puzzle[vi[i][j]].vs.size();k++){
// cout<<puzzle[vi[i][j]].vs[k];
// }
cout<<vi[i][j];
}
cout<<endl;
}
}
}
int main(){
int n;
cin>>n;
for(int count=0;count<n;count++){//main
int x,y,z;
cin>>x>>y>>z;
char buff[256];
cin.getline(buff,256);
int square_size=x*x;
piece puzzle[square_size];
for(int i=0;i<square_size;i++){
for(int j=0;j<y;j++){
cin.getline(buff,256);
string details(buff);
puzzle[i].vs.push_back(details);
}
int t,l,b,r;
cin>>t>>l>>b>>r;
cin.getline(buff,256);
cin.getline(buff,256);
puzzle[i].top=t;
puzzle[i].left=l;
puzzle[i].bottom=b;
puzzle[i].right=r;
}
/*//check input
for(int i=0;i<square_size;i++){
for(int j=0;j<puzzle[i].vs.size();j++){
cout<<puzzle[i].vs[j];
cout<<endl;
}
cout<<puzzle[i].top<<" "<<puzzle[i].left<<" "<<puzzle[i].bottom<<" "<<puzzle[i].right<<endl;
}
*/
int start,topright,botleft,botright;
vector< vector<int> > vi;
for(int i=0;i<x;i++){
vector<int> v;
vi.push_back(v);
for(int j=0;j<x;j++){
vi[i].push_back(-1);
}
}
for(int i=0;i<square_size;i++){
if(puzzle[i].top==0 && puzzle[i].left==0){
start=i;
}
if(puzzle[i].top==0 && puzzle[i].right==0){
topright=i;
}
if(puzzle[i].bottom==0 && puzzle[i].left==0){
botleft=i;
}
if(puzzle[i].bottom==0 && puzzle[i].right==0){
botright=i;
}
}
vi[0][0]=start;
// vi[0][x-1]=topright;
// vi[x-1][0]=botleft;
// vi[x-1][x-1]=botright;
bool used[square_size];
for(int i=0;i<square_size;i++){
used[i]=false;
}
recur(vi,puzzle,used,square_size,0,0);
}
return 1;
}