Swapping Game

Dongil came up with a game he can play by himself.

The game starts from one string of $N$ lowercase letters.

Dongil may swap any two letters of the string. He may repeat this operation as many times as he likes, zero times included.

The goal is to build the lexicographically smallest string.

After a few rounds the game felt too easy, so Dongil added one more rule. For every position of the finished string he decides in advance which letters may sit there, like this.

• The first letter must be a or b.
• The second letter must be b or c.

The rule applies only to the final string. A string that appears in the middle of the game does not have to obey it.

The rule made the game much harder. Help Dongil and find the lexicographically smallest string he can build while obeying the rule.

The first line has the number of test cases $T$. ($1 \le T \le 100$)

The first line of each test case has the starting string $S$, which consists of $N$ lowercase letters. ($1 \le N \le 100$)

The next $N$ lines each have a string $C_i$. $C_i$ consists of $L_i$ letters and lists the letters allowed at position $i$ of the result. ($1 \le L_i \le 5$)

Every letter that appears in $C_i$ appears at least once in the starting string $S$.

For each test case print, on its own line, the lexicographically smallest string that obeys the rule. If no string obeys the rule, print NO SOLUTION.