Description

假设我们有一个边长为 $W$ 的正方形网格，因此总共有 $W^2$ 个格子。我们进一步规定，每个格子可以填入以下内容之一：

• 一个 $0$ 到 $9$ 的数字；
• 加号（+）；
• 减号（-）。

如果我们再加上如下约束：任意两个数字不能在水平方向或竖直方向相邻，任意两个运算符（+ 或 -）也不能在水平方向或竖直方向相邻，那么这样的正方形就称为一个“算术方格”。

Square Math 是这样一种谜题：给定一个算术方格，我们可以从任意一个数字格子出发，每次可以水平或竖直移动一格，最终在一个数字格子结束。我们按照经过的格子的内容，拼接成一个数学表达式并计算其值。例如：

2+3
+4-
1+0

上面是一个 $W=3$ 的合法算术方格。如果我们从“2”出发，向右水平移动，再向下垂直移动，就得到“2+4”，其值为 $6$。如果我们再向右水平移动，再向上垂直移动，就得到“2+4-3”，其值为 $3$。

在 Square Math 中，对同一个格子的使用次数没有限制。也就是说，可以从某个格子移动到相邻格，再返回原格，这样的路径是允许的。给定一个算术方格和若干个查询值，请你为每个查询值找到一个 Square Math 路径，使得对应的表达式计算结果等于该值。

Input Format

第一行是一个整数 $T$，表示测试用例数。接下来有 $T$ 组测试数据。每组测试数据的第一行包含两个整数 $W$ 和 $Q$。接下来 $W$ 行，每行 $W$ 个字符，表示算术方格。保证所有输入的算术方格都是合法的。再接下来一行，包含 $Q$ 个用空格分隔的整数，表示需要通过 Square Math 得到的目标值（查询）。保证每个目标值至少有一种合法的 Square Math 表达式可以实现。

Output Format

对于每组测试数据，先输出一行 "Case #$X$:"，其中 $X$ 是测试编号（从 1 开始）。然后对于本组中的每个查询，输出一行对应的 Square Math 表达式。

如果有多种可能的表达式，输出最短的那一个。如果仍有多个最短表达式，输出字典序最小的那个。注意，'+' 的字典序小于 '-'。

2
5 3
2+1-2
+3-4+
5+2+1
-4-0-
9+5+1
20 30 40
3 2
2+1
+4+
5+1
2 20

Case #1:
1+5+5+9
3+4+5+9+9
4+9+9+9+9
Case #2:
2
5+5+5+5

Hint

限制条件

• $1 \leq T \leq 60$

小数据集

• 时间限制：3 秒
• $2 \leq W \leq 10$
• $1 \leq Q \leq 20$
• $1 \leq$ 每个查询 $\leq 50$

大数据集

• 时间限制：12 秒
• $2 \leq W \leq 20$
• $1 \leq Q \leq 50$
• $1 \leq$ 每个查询 $\leq 250$

翻译由 ChatGPT-4.1 完成。