스와이퍼 키보드

스와이퍼 키보드는 터치스크린 휴대폰에 쓰는 키보드다. 입력할 단어의 글자를 하나씩 누르는 대신, 선분 하나 이상이 이어진 꺾인 선을 한 번에 그린다.

이 문제의 키보드는 정사각형 키가 네 줄로 놓여 있다. 키는 모두 가로와 세로가 1인 정사각형이고, 중심은 항상 좌표가 정수인 점이다. 좌표 $x$는 오른쪽으로 갈수록 커지고, 좌표 $y$는 아래로 갈수록 커진다.

위쪽 두 줄은 키가 여섯 개씩 놓여 $x=0$부터 $x=5$까지 이어지고, 아래쪽 두 줄은 키가 일곱 개씩 놓여 $x=-1$부터 $x=5$까지 이어진다.

이 키보드는 널리 쓰이는 실제 제품과 똑같이 동작하지 않는다. 문제에 적히지 않은 성질은 가정하면 안 된다.

꺾인 선은 알파벳 대문자 두 개 이상으로 이루어진 문자열로 나타내고, 이어진 두 글자는 항상 다르다. 선은 첫 글자의 중심에서 출발해 다음 글자의 중심으로 차례차례 이어진다. 문자열 ACM은 A의 중심에서 출발해 C의 중심을 지나 M의 중심으로 가는 선을 뜻한다.

이렇게 그린 선은 다른 키 위도 지나간다. A와 C 사이에서는 B를 지나고, C와 M 사이에서는 B, H, G, N을 이 순서로 지난다. 선이 지나는 키를 지나는 순서대로 모두 적으면 그 꺾인 선의 확장 문자열이 된다. 위 예에서는 ABCBHGNM이다. 이 선을 그린 사람은 확장 문자열의 부분 수열인 단어를 뜻할 수 있으므로, ACM이나 BGN, ABCBHGNM처럼 어떤 부분 수열이든 의도한 단어가 될 수 있다.

문자열 X가 문자열 Y의 부분 수열이라는 말은, Y에서 글자 0개 이상을 지우고 남은 글자의 순서를 그대로 두어 X를 만들 수 있다는 뜻이다.

단어 하나 이상으로 이루어진 사전과 꺾인 선을 나타내는 문자열이 주어진다. 이 꺾인 선이 뜻할 수 있는 단어를 사전에서 찾아라.

키 안으로 들어가지 않고 경계선만 따라가는 선은 그 키를 지난 것으로 보지 않는다. A에서 H로 가는 선분은 B도 G도 지나지 않는다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스의 첫째 줄에는 사전에 든 단어의 개수 $N$과 꺾인 선을 나타내는 문자열 $P$가 공백 하나로 구분되어 주어진다 ($1 \le N \le 1000$). 이어지는 $N$개 줄에는 사전의 단어가 한 줄에 하나씩 주어진다.

입력에 주어지는 문자열은 모두 알파벳 대문자 A부터 Z까지로만 이루어지고, 길이는 2 이상 100 이하다.

꺾인 선을 나타내는 문자열은 선분만 설명하므로, 선이 지나는 키가 모두 들어 있지는 않다. 한 꺾인 선이 같은 키를 여러 번 지날 수도 있지만, 이어진 두 글자는 절대 같지 않다.

각 테스트 케이스마다 한 줄을 출력한다. 주어진 꺾인 선의 확장 문자열의 부분 수열인 단어 가운데 입력에 가장 먼저 나온 단어를 출력한다. 그런 단어가 사전에 없으면 NO SOLUTION을 출력한다.