시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 104 21 20 33.333%

문제

단어 찾기 게임은 알파벳으로 이루어진 그리드 판과 단어들의 리스트를 가지고 시작하는 게임이다. 게임의 목적은 그리드 판에서 리스트에 있는 단어를 모두 찾는것이다! 그리드 판에서 단어를 찾을 때는, 해당 단어가 그리드 판에서 연속적으로 가로,세로 또는 대각선 상의 같은 선상에 존재하여야 한다. 해당 규칙으로 그리드 내에서 단어를 찾으면, 해당 단어를 그리드 내에 마킹한다. 단, 그리드 내의 한 글자가 여러 단어에 의해서 여러번 마킹될 수 있음에 유의하라.

같은 방식으로 리스트 내의 모든 단어를 찾고 그리드에 표시를 했으면 ,그리드를 위에서 아래로, 왼쪽에서 오른쪽으로 훑으면서 마킹되지 않은 글자를 적는다. 최종적으로 적혀진 글자를 solution이라고 한다.

세일이는 이 게임에 도전하려고 했으나 시력이 안좋아 그리드 내의 글자를 분간하기에는 어렵다. 세일이가 이 게임을 해결할 수 있도록 도와주자! 리스트 내의 모든 단어가 그리드 내에 존재하는지 여부를 체크해보자. 단, 리스트 내의 한 단어가 그리드 내에 두번 등장할 때에 유의하여야 한다.

입력

입력의 첫번째 줄에는 테스트케이스의 개수 T(≤ 100)가 들어온다. 각 테스트케이스의 첫번째 줄에는 세개의 정수 n, h, w가 입력으로 들어온다. (1 ≤ n ≤ 256, 1 ≤ h, w ≤ 32) n은 리스트 내 단어의 개수이고 h, w는 각각 그리드의 높이와 너비이다.

이어지는 h줄에는 그리드를 나타내는 알파벳 대문자 w개가 입력으로 들어온다

이어지는 n줄에는 그리드 내에서 찾아야 하는 단어 n개가 입력으로 들어온다. 각 단어는 최대 32글자이며, 영어 대문자로만 구성되어 있다.

 

출력

각 테스트 케이스마다 규칙에 따라 게임을 진행했을 때 얻을 수 있는 solution을 출력한다. 만약 단어 리스트 중 그리드에 나타나지 않는 단어가 있을 경우에는 "no solution"을 출력한다. 대신, 단어 리스트 내의 모든 단어가 그리드에 나타나지만, 그리드 내의 다른 위치에서 2번이상 발견되는 단어가 있다면 "ambiguous"를 출력한다. 만약 모든 단어가 그리드 내에 나타나지만, 최종적으로 그리드 내에 마킹되지 않은 글자가 없는 경우에는 "empty solution"을 출력한다.

예제 입력

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

예제 출력

ALGORITHMS
ambiguous
no solution
BAPC

힌트