Puzzlestan

There are $N$ kinds of items and $M$ guests. Each guest owns exactly one item of every kind (for example, each guest checks in one overcoat, one hat, and so on). Hence there are $N \times M$ items in total, and each item has a distinct single-letter name (letters are case-sensitive).

The $M$ items of kind $i$ ($1 \le i \le N$) are written as a string of length $M$, called the $i$-th group. The $j$-th character of this string is the $j$-th item of group $i$.

You are given several statements telling, for two items, whether they belong to the same guest or to different guests. Each statement is one of:

• The two items belong to the same guest.
• The two items belong to different guests.

Using these statements, determine which guest owns each item. The statements always determine the assignment uniquely.

The first line contains the number of test cases (at most $20$).

The first line of each test case contains two positive integers $N$ and $M$, where $N$ ($1 \le N \le 7$) is the number of item kinds and $M$ ($1 \le M \le 7$) is the number of guests. Each of the next $N$ lines contains one string of length $M$ representing a group (the distinct items of one kind).

After that come several statement lines. Each statement has the form i j X k r, meaning that the $j$-th item of group $i$ and the $r$-th item of group $k$ belong to the same guest if $X$ is R, or to different guests if $X$ is N. The last line of each test case is the dummy statement 0 0 R 0 0.

For each test case, print $M$ lines. Line $g$ ($1 \le g \le M$) describes the guest identified by the $g$-th item of the first group: print that guest's item from group 1, then from group 2, ..., then from group $N$, as letters with no separator. Thus the first character of each line matches the first group in order.

Separate the output of consecutive test cases by exactly one blank line.