사각수식 (작은 입력)

문제

한 변에 칸이 $W$ 개씩 있는 정사각형 판을 생각한다. 칸은 모두 $W^2$ 개다. 각 칸에는 다음 중 하나를 적는다.

0부터 9까지의 숫자 하나
덧셈 기호 +
뺄셈 기호 -

여기에 조건을 하나 더 붙인다. 가로나 세로로 맞닿은 두 칸이 모두 숫자여서는 안 되고, 가로나 세로로 맞닿은 두 칸이 모두 기호(+ 또는 -)여서도 안 된다. 이 조건을 지킨 판을 산술 정사각형이라고 부른다.

사각수식은 산술 정사각형에서 하는 퍼즐이다. 숫자 칸에서 출발해 가로나 세로로 한 칸씩 움직이고, 숫자 칸에서 멈춘다. 지나온 문자를 순서대로 이어 붙이면 수식이 되고, 이 수식을 왼쪽부터 차례로 계산하면 값 하나가 정해진다. 예를 보자.

2+3
+4-
1+0

이 판은 $W = 3$ 인 산술 정사각형이다. 왼쪽 위 2에서 출발해 오른쪽으로 한 칸, 이어서 아래로 한 칸 움직이면 2+4가 되고 값은 6이다. 여기서 오른쪽으로 한 칸, 위로 한 칸 더 움직이면 2+4-3이 되고 값은 3이다.

같은 칸은 몇 번이든 다시 지나도 된다. 옆 칸으로 갔다가 곧바로 원래 칸으로 돌아오는 것도 규칙에 맞는다. 산술 정사각형과 질의 목록이 주어질 때, 각 질의 값과 같은 값이 되는 사각수식을 구하라.

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫째 줄에는 두 정수 $W$ 와 $Q$ 가 주어진다. 다음 $W$ 개 줄에는 각각 $W$ 개의 문자가 주어져 산술 정사각형을 이룬다. 입력으로 주어지는 판은 모두 위 조건을 만족한다. 그다음 줄에는 사각수식으로 만들어야 하는 값 $Q$ 개가 공백으로 구분되어 주어진다. 이 값을 질의라고 부른다. 주어지는 모든 질의에는 그 값이 되는 사각수식이 적어도 하나 있다.

제한

$1 \le T \le 60$
$2 \le W \le 10$
$1 \le Q \le 20$
각 질의는 $1$ 이상 $50$ 이하

출력

각 테스트 케이스마다 먼저 Case #X:를 한 줄에 출력한다. $X$ 는 테스트 케이스 번호이고 1부터 시작한다. 그다음 그 테스트 케이스의 질의를 입력에 주어진 순서대로 처리하면서, 질의 값과 같은 값이 되는 사각수식을 한 줄에 하나씩 출력한다.

가능한 사각수식이 여러 개라면 길이가 가장 짧은 것을 출력한다. 가장 짧은 것이 여럿이면 사전순으로 가장 앞서는 것을 출력한다. 길이가 같은 수식은 숫자와 기호가 놓이는 자리가 서로 같으므로, 비교할 때는 +가 -보다 앞선다는 점만 기억하면 된다.