접두 부호

샘은 바깥 세상과 연결되는 오래된 통신 채널을 발견했다. 이 채널은 매우 느리기 때문에, 샘과 친구들은 메시지를 더 빠르게 보내기 위해 압축 부호를 사용하려 한다. 고심 끝에 샘은 이진 접두 부호(binary prefix code)를 쓰기로 한다.

접두 부호란, 어떤 부호어도 다른 부호어의 접두사가 되지 않는 가변 길이 부호를 말한다. 예를 들어 {a=0, b=10, c=11}은 접두 부호이지만, {a=0, b=10, c=01}은 0이 01의 접두사이므로 접두 부호가 아니다.

이진 접두 부호(부호어가 0과 1로 이루어진 부호)는 이진 트리로 나타낼 수 있다. 이때 기호는 잎(leaf)에 놓이고, 루트에서 잎까지 가는 경로가 그 기호의 부호어가 된다. 편의상 왼쪽 자식으로 가면 0, 오른쪽 자식으로 가면 1이 붙는다고 하자. 예를 들어 접두 부호 {a=0, b=10, c=11}과 {a=000, b=001, c=01, d=10, e=110, f=111}은 아래와 같은 이진 트리로 그릴 수 있다.

이진 트리는 문자열로 간결하게 나타낼 수도 있다. 길이가 $N$인 문자열을 위치 $0$부터 $N-1$까지의 문자열이라고 보자. 루트는 위치 $0$에 있고, 위치 $k$에 있는 노드의 왼쪽 자식과 오른쪽 자식은 각각 위치 $2k+1$과 $2k+2$에 있다. 이 규칙에 따르면 위의 두 트리는 각각 문자열 *a***bc와 ****cd*ab****ef로 나타낼 수 있으며, 여기서 *는 내부(잎이 아닌) 노드나 비어 있는 노드를 뜻한다.

압축된 메시지를 해독할 때는 루트에서 출발하여, 다음 비트가 0이면 왼쪽 자식으로, 1이면 오른쪽 자식으로 이동한다. 잎에 도달하면 그 기호를 출력하고, 다시 루트에서 시작하여 남은 메시지를 이어서 해독한다.

문자열 형태의 접두 부호와 여러 개의 이진 메시지가 주어질 때, 각 메시지를 원래의 문자열로 해독하여라.

첫째 줄에는 테스트 케이스의 수 $T$ ($T < 100$)가 주어진다. 이후 각 줄에는 하나의 테스트 케이스가 주어지며, 먼저 해독할 메시지의 개수 $k$가 주어지고, 이어서 접두 부호의 문자열 표현이, 그다음에 해독할 $k$개의 이진 메시지가 주어진다. 모든 메시지는 주어진 접두 부호에 등장하는 기호들만으로 이루어져 있음이 보장된다.

각 테스트 케이스마다, 해독된 메시지들을 하나의 공백으로 구분하여 한 줄에 출력한다.