사각형 수식 (큰 입력)

문제

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

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

여기에 조건을 하나 더 붙인다. 가로나 세로로 맞닿은 두 칸에 숫자가 함께 오지 않고, 가로나 세로로 맞닿은 두 칸에 연산 기호가 함께 오지 않는다. 이 조건을 지킨 판을 산술 사각형이라고 부른다.

산술 사각형 하나가 주어지면 다음 퍼즐을 풀 수 있다. 숫자 칸 하나에서 출발해 한 번에 한 칸씩 가로나 세로로 움직이고, 숫자 칸에서 멈춘다. 지나간 칸의 문자를 순서대로 이어 쓰면 수식이 되고, 이 수식을 왼쪽에서 오른쪽으로 계산하면 값 하나가 나온다. 이 퍼즐의 이름이 사각형 수식이다.

아래는 $W = 3$ 인 산술 사각형이다.

2+3
+4-
1+0

왼쪽 위의 2에서 출발해 오른쪽으로 한 칸, 아래로 한 칸 움직이면 2+4가 되고 값은 6이다. 여기서 오른쪽으로 한 칸, 위로 한 칸 더 움직이면 2+4-3이 되고 값은 3이다.

한 칸은 몇 번이든 다시 지날 수 있다. 어떤 칸에서 이웃 칸으로 갔다가 곧바로 원래 칸으로 돌아오는 이동도 허용한다. 한 번도 움직이지 않고 숫자 칸 하나로만 이루어진 수식도 유효하다.

산술 사각형과 값 목록이 주어진다. 각 값을 만드는 사각형 수식을 찾아라.

입력

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에 두 정수 $W$ 와 $Q$ 가 주어진다. 다음 $W$ 개의 줄에는 각각 $W$ 개의 문자가 주어지고, 이것이 산술 사각형이다. 입력에 주어지는 산술 사각형은 모두 위 조건을 지킨 판이다. 그다음 줄에 사각형 수식으로 만들어야 하는 값 $Q$ 개가 공백으로 구분되어 주어진다. 주어지는 값은 모두 사각형 수식으로 만들 수 있다.

제한

$1 \le T \le 60$
$2 \le W \le 20$
$1 \le Q \le 50$
각 값은 $1$ 이상 $250$ 이하의 정수

출력

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

값을 만드는 사각형 수식이 여러 개면 가장 짧은 것을 출력한다. 가장 짧은 것이 여러 개면 그중 사전순으로 가장 앞선 것을 출력한다. +는 -보다 사전순으로 앞선다.