Word Search

Interview

Time limit1sMemory limit256 MB

Summary

Find each listed word in the letter grid in any of eight directions and output leftover letters, or report missing or ambiguous placements.

Level: Medium5 of 10
Topics: String matching, Matrix, Brute force
Solved: No attempts yet

Problem

Given a letter grid and a word list, every word must appear in one of eight directions. If any word is missing, print no solution. If any word has more than one distinct placement, print ambiguous. Otherwise print the unmarked letters in row-major order, or empty solution if none remain.

Input

The first line contains the number of test cases. Each test gives $n$ , $h$ , $w$ , the $h \times w$ grid, and $n$ words.

Output

For each test case, print the solution string or one of the three special answers.

Examples1

Example 1

Input

4
10 7 8
ELIPMOCN
TACODEOL
IMELBORP
MGOALRRM
BIPLEIEA
UCATZUCE
SBHEMSTT
BAPC
TUE
TEAM
PROBLEM
CODE
COMPILE
SUBMIT
CORRECT
BALLOON
PRIZE
2 4 3
BCB
AOA
PDP
CEC
BAPC
CODE
3 4 3
BCB
AOA
PDP
CEC
BAPC
CODE
TEAM
2 2 10
DELEVELEDB
ATESTSETPC
DELEVELED
TESTSET

Expected output

ALGORITHMS
ambiguous
no solution
BAPC