题目描述

杰登是一个痴迷于数字的数学极客！他最爱的数字是一个 $m$ 位的字符串 $x$。吉夫给了他另外 $n$ 个 $m$ 位的字符串 $v[1], v[2], \ldots, v[n]$。这些字符串（包括 $x$）中的所有数字范围都是 $0$ 到 $k-1$，其中 $k$ 是一个给定的整数（$2 \le k \le 10$）。用 $v[i][j]$ 表示 $v[i]$ 从左起的第 $j$ 位数字。

由于杰登非常喜爱他的最爱数字 $x$，他希望使用数字转换机将吉夫给他的所有 $n$ 个数字都转换成数字 $x$。对 $v[i]$ 的一次操作如下：

• 选择两个整数 $l$ 和 $r$，满足 $1 \le l \le r \le m$。
• 对于每个 $l \le j \le r$，将 $v[i][j]$ 的值设置为 $(v[i][j] + a[j]) \mod k$。

其中 $a$ 是一个给定的长度为 $m$ 的数组。$p \bmod q$ 表示 $p$ 除以 $q$ 的余数（例如，$5 \bmod 2 = 1$）。该操作的成本为 $c[l] + c[r]$ 美元（特别地，如果 $l = r$，成本为 $c[l] + c[l]$），其中 $c$ 是一个给定的长度为 $m$ 的数组。更多细节请参考样例测试用例。

对于每个 $v[i]$，帮助杰登 独立地 解决以下问题：

• 使用任意次操作将 $v[i]$ 转换为 $x$ 所需的最小总成本（以美元计）是多少？

如果无法将 $v[i]$ 转换为 $x$，则输出 $-1$。

输入格式

你的程序必须从标准输入中读取数据。

输入的第一行包含三个以空格分隔的整数 $n$、$m$ 和 $k$。

输入的第二行包含 $m$ 个以空格分隔的整数 $a[1], a[2], \ldots, a[m]$。

输入的第三行包含 $m$ 个以空格分隔的整数 $c[1], c[2], \ldots, c[m]$。

输入的第四行包含一个整数 $x$。

接下来的 $n$ 行，每行包含一个整数。第 $i$ 行包含 $v[i]$。

输出格式

你的程序必须输出到标准输出。

输出应包含 $n$ 行，每行一个整数。第 $i$ 行应包含将 $v[i]$ 转换为 $x$ 所需的最小总成本。如果不可能，则输出 $-1$。

6 3 8
1 2 3
3 1 4
676
356
431
676
767
133
715

16
42
0
-1
25
37

3 4 2
1 1 1 1
1 1 1 1
1001
1110
1100
0110

2
4
2

1 1 10
1
67
6
7

1206

1 2 10
1 1
1 1000000000
24
83

1000000007

提示

样例测试用例 1 解释

杰登的最爱数字是 $x = 676$。

考虑 $v[1] = 356$。以下 3 次操作的序列可以将 356 转换为 676：

$$\underline{356} \xrightarrow{l=1,\ r=2} \underline{476} \xrightarrow{l=1,\ r=1} \underline{576} \xrightarrow{l=1,\ r=1} \underline{676}$$

1. $l = 1, r = 2$：第 1 位和第 2 位分别变为 $(3 + 1) \mod 8 = 4$ 和 $(5 + 2) \mod 8 = 7$。成本为 $c[1] + c[2] = 3 + 1 = 4$ 美元。

2. $l = 1, r = 1$：第 1 位变为 $(4 + 1) \mod 8 = 5$。成本为 $c[1] + c[1] = 3 + 3 = 6$ 美元。

3. $l = 1, r = 1$：第 1 位变为 $(5 + 1) \mod 8 = 6$。成本为 6 美元。

三次操作的总成本为 $4 + 6 + 6 = 16$ 美元。可以证明不存在其他总成本更低的操作序列。

对于 $v[3] = 676$，无需进行任何操作，因为该数字已经等于 $x$。因此，最小总成本为 0 美元。

对于 $v[4] = 767$，可以证明不存在任何操作序列能将 767 转换为 676。因此，输出 $-1$。

子任务

对于所有测试用例，输入均满足以下范围：

• $1 \le n \le 200000$
• $1 \le m \le 5$
• $2 \le k \le 10$
• 对于所有 $1 \le i \le m$，$1 \le a[i] \le k - 1$
• 对于所有 $1 \le i \le m$，$1 \le c[i] \le 10^9$
• $x, v[1], v[2], \ldots, v[n]$ 均为 $m$ 位字符串，每个数字的取值范围为 $0$ 到 $k - 1$（包含端点）。它们可能包含前导零。

你的程序将在满足以下限制的输入实例上进行测试：

子任务	分值	附加约束
0		样例测试用例
1	5	$m = 1$ 且对于所有 $1 \le i \le m$，有 $a[i] = 1$
2	13	$m = 2$ 且对于所有 $1 \le i \le m$，有 $a[i] = 1$
3	10	$k = 2$ 且 $c[1] = c[2] = \cdots = c[m]$
4	16	$c[1] = c[2] = \cdots = c[m]$
5	24	$n \le 20$
6	32	无额外约束

翻译由 DeepSeek 完成