#include<stdio.h>
#include<string.h>
char  item[10][10];
char  ans[10][10];
int  n, guests, s;

struct relation
{
	char a, b, x;
}r[1000];   //struct of relations

int  flag[10][10], ok;


void  init()
{
	int  i, j, ii, jj;
	char  c;
	memset(ans, 0, sizeof(ans));
	memset(flag, 0, sizeof(flag));
	ok = 0;
	s = 0;    //关系数目
	scanf("%d %d", &n, &guests);
	for(i = 0;  i < n; i++)
		scanf("%s", item[i]);
	while(scanf("%d %d %c %d %d", &i, &j, &c, &ii, &jj) && i)
	{
		r[s].a = item[i-1][j-1];
		r[s].b = item[ii-1][jj-1];
		r[s++].x = c;
	}
	
}

void  print()
{
	int  i;
	for(i = 0; i < guests; i++)
		printf("%s\n", ans[i]);
}

void  solve(int g, int t)
{
	int  i, j, k;
	char a, b;
	bool  hash[10][10];
	
	if(ok) return ;
	if(g == guests)
	{
		print();
		ok = 1;
	}
	else  if(t == n)
	{
		//printf("%s\n", ans[g]);
		solve(g+1, 0);
	}
	else
	{
		memset(hash, 0, sizeof(hash));
		//三重循环找，是否存在已要求的关系
		for(i = 0; i < guests; i++)			// t类-hang，guests种物品
		{
			a = item[t][i];
			//if(flag[t][i])
			for(j = 0; j < t; j++)     //t-1 of ans[g]
			{
				b = ans[g][j];
				for(k = 0; k < s; k++)    //s relations
				{
					if((r[k].a == a && r[k].b == b) || (r[k].a == b && r[k].b == a))
					{
						if(r[k].x == 'R')
						{
							if(flag[t][i]) return ;
							else
							{
								ans[g][t] = item[t][i];
								flag[t][i] = 1;
								solve(g, t+1);
								flag[t][i] = 0;
								return ;
							}
						}
						else  hash[t][i] = 1;   //hash标记N关系
					}
				}
			}
		}

		//else search for ..
		for(i = 0; i < guests; i++)
		{
			if(!hash[t][i] && !flag[t][i])
			{
				ans[g][t] = item[t][i];
				flag[t][i] = 1;
				solve(g, t+1);
				flag[t][i] = 0;
			}
		}
	}
	
}
int  main()
{
	int  cs;
	scanf("%d", &cs);
	while(cs--)
	{
		init();
		solve(0,0);
	}
	return 0;
}