Jayden 是一个对数字着迷的数学迷！他最喜欢的数字是一个 $m$ 位的字符串 $x$。Ziv 给了他另外 $n$ 个 $m$ 位的字符串 $v[1], v[2], \dots, v[n]$。这些字符串（包括 $x$）中的所有数位都在 $0$ 到 $k - 1$ 的范围内，其中 $k$ 是一个给定的整数（$2 \le k \le 10$）。设 $v[i][j]$ 表示 $v[i]$ 从左往右数第 $j$ 个数位。
由于 Jayden 非常喜欢他最喜欢的数字 $x$，他希望使用一台数字转换机，将 Ziv 给他的所有 $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]) \bmod 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]$，请帮助 Jayden 独立解决以下问题：
- 使用任意次数的操作，将 $v[i]$ 转换为数字 $x$ 所需的最小总代价（以元为单位）是多少？
如果无法将 $v[i]$ 转换为 $x$，则输出 $-1$。
输入格式
你的程序必须从标准输入中读取。
输入的第一行包含三个空格分隔的整数 $n$，$m$ 和 $k$。
输入的第二行包含 $m$ 个空格分隔的整数 $a[1], a[2], \dots, a[m]$。
输入的第三行包含 $m$ 个空格分隔的整数 $c[1], c[2], \dots, c[m]$。
输入的第四行包含一个整数 $x$。
接下来的 $n$ 行，每行包含一个整数。其中第 $i$ 行包含 $v[i]$。
输出格式
你的程序必须输出到标准输出。
输出应包含 $n$ 行，每行包含一个整数。其中第 $i$ 行应包含将 $v[i]$ 转换为 $x$ 所需的最小总代价。如果这是不可能的，则输出 $-1$。
子任务
对于所有测试用例，输入将满足以下范围：
- $1 \le n \le 200\,000$
- $1 \le m \le 5$
- $2 \le k \le 10$
- $1 \le a[i] \le k - 1$ 对于所有 $1 \le i \le m$
- $1 \le c[i] \le 10^9$ 对于所有 $1 \le i \le m$
- $x, v[1], v[2], \dots, v[n]$ 均为 $m$ 位字符串，其中每个数位的范围在 $0$ 到 $k - 1$ 之间（含两端）。它们可能包含前导零。
你的程序将在满足以下限制的输入实例上进行测试：
| 子任务 | 分值 | 附加限制 |
|---|---|---|
| 0 | 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] = \dots = c[m]$ |
| 4 | 16 | $c[1] = c[2] = \dots = c[m]$ |
| 5 | 24 | $n \le 20$ |
| 6 | 32 | 无附加限制 |
样例
输入样例 1
6 3 8 1 2 3 3 1 4 676 356 431 676 767 133 715
输出样例 1
16 42 0 -1 25 37
说明 1
Jayden 最喜欢的数字是 $x = 676$。
考虑 $v[1] = 356$。以下由 3 步操作组成的序列可以将 $356$ 转换为 $676$：
$$356 \xrightarrow{l=1, r=2} 476 \xrightarrow{l=1, r=1} 576 \xrightarrow{l=1, r=1} 676$$
- $l = 1, r = 2$：第 1 位和第 2 位分别变为 $(3 + 1) \bmod 8 = 4$ 和 $(5 + 2) \bmod 8 = 7$。这花费 $c[1] + c[2] = 3 + 1 = 4$ 元。
- $l = 1, r = 1$：第 1 位变为 $(4 + 1) \bmod 8 = 5$。这花费 $c[1] + c[1] = 3 + 3 = 6$ 元。
- $l = 1, r = 1$：第 1 位变为 $(5 + 1) \bmod 8 = 6$。这花费 $6$ 元。
这三次操作的总代价为 $4 + 6 + 6 = 16$ 元。可以证明，不存在其他代价更低的操作序列。
对于 $v[3] = 676$，由于该数字已经等于 $x$，因此不需要进行任何操作。因此，最小总代价为 $0$ 元。
对于 $v[4] = 767$，可以证明不存在任何操作序列可以将 $767$ 转换为 $676$。因此，输出 $-1$。
输入样例 2
3 4 2 1 1 1 1 1 1 1 1 1001 1110 1100 0110
输出样例 2
2 4 2
输入样例 3
1 1 10 1 67 6 7
输出样例 3
1206
输入样例 4
1 2 10 1 1 1 1000000000 24 83
输出样例 4
1000000007