정사각형 수학

각 변에 W개의 칸이 있어 전체 칸 수가 $W^{2}$개인 정사각형이 있다고 하자. 더 나아가 각 칸을 다음 중 하나로 채우자.

• 0부터 9까지의 숫자 하나;

• 덧셈 기호(+);

• 뺄셈 기호(-). 마지막으로, 가로 또는 세로로 인접한 숫자가 2개도 없고 가로 또는 세로로 인접한 연산자(+ 또는 -)가 2개도 없다는 제약을 추가하면, 이 정사각형을 "산술 정사각형"이라고 부를 수 있다.

Square Math은 산술 정사각형이 주어졌을 때 임의의 숫자 칸에서 시작하여 한 번에 한 칸씩 가로 또는 세로로 이동한 뒤 마지막에는 숫자 칸에서 끝나는 퍼즐의 이름이다. 이동 과정에서 얻은 수학식을 계산하여 하나의 값을 얻는다. 예를 들면 다음과 같다.

2+3
+4-
1+0

위 정사각형은 크기가 W = 3인 올바른 산술 정사각형이다. "2"에서 시작해 가로로 오른쪽으로 이동한 다음 세로로 아래로 이동하면 "2+4"을 얻으며, 그 값은 "6"이다. 여기서 다시 가로로 오른쪽으로 이동한 다음 세로로 위로 이동하면 "2+4-3"을 얻으며, 이는 "3"과 같다.

정사각형 수학에서는 특정 칸을 사용할 수 있는 횟수에 제한이 없다. 한 칸에서 이웃 칸으로 이동한 다음 원래 칸으로 돌아오는 것도 완전히 허용된다. 산술 정사각형과 질의 목록이 주어질 때, 각 질의의 값이 되는 Square Math 식을 찾는 것이 당신의 임무이다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 60

소규모 데이터 세트

시간 제한: 30초. 2 ≤ W ≤ 10 1 ≤ Q ≤ 20 1 각 질의 ≤ ≤ 50

대규모 데이터 세트

시간 제한: 60초. 2 ≤ W ≤ 20 1 ≤ Q ≤ 50 1 각 질의 ≤ ≤ 250

입력의 첫 번째 줄에는 정수 T 하나가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 정수 2개인 W와 Q가 주어진다. 이어지는 W개의 줄에는 각각 산술 정사각형을 나타내는 W개의 문자가 주어진다. 걱정하지 않아도 된다. 입력으로 주어지는 모든 산술 정사각형은 올바르게 구성되어 있다. 그다음 줄에는 Square Math을 사용해 계산해야 하는 값(질의)을 나타내는 Q개의 정수 목록이 공백으로 구분되어 주어진다. 주어진 모든 값에는 가능한 Square Math 해가 적어도 하나 있다고 가정해도 된다.

각 테스트 케이스에 대해 먼저 한 줄에 "Case #X:"을 출력한다. 여기서 X는 1부터 시작하는 테스트 케이스 번호이다. 그런 다음 테스트 케이스의 각 질의에 대해, 그 질의의 값이 되는 Square Math 식을 한 줄에 하나씩 출력한다.

가능한 Square Math 식이 여러 개라면 가장 짧은 것을 출력한다. 그래도 동률이면 사전순으로 가장 작은 식을 출력한다. '+'가 '-'보다 사전순으로 작다는 점을 기억하라.