← 返回题目列表

Codeforces · 1431/I

I. 循环移位

中文机器翻译题面 查看原题

给定一个由 $$$n$$$ 行和 $$$m$$$ 列组成的矩阵。该矩阵包含拉丁字母表的小写字母。

您可以执行任意次数的以下操作:选择两个整数 $$$i$$$ ($$$1 \le i \le m$$$) 和 $$$k$$$ ($$$0 < k < n$$$),然后将每列 $$$j$$$ 移位,使得 $$$i \le j \le m$$$ 循环移动 $$$k$$$。移位是向上执行的。

例如,如果您有一个矩阵

$$$\left( \begin{array} \\ a & b & c \\ d & e & f \\ g & h & i \end{array}\right) $$$

$$$\left( \begin{array} \\ a & e & f \\ d & h & i \\ g & b & c \end{array}\right) $$$

您必须处理 $$$q$$$ 查询。每个查询都是一个长度为 $$$m$$$ 的字符串,由拉丁字母的小写字母组成。对于每个查询,您必须计算必须执行的上述操作的最少数量,以便矩阵的至少一行等于查询中的字符串。请注意,所有查询都是独立的,即您在一个查询中执行的操作不会影响其他查询中的初始矩阵。

输入

第一行包含三个整数 $$$n$$$, $$$m$$$, $$$q$$$ ($$$2 \le n, m, q \le 2.5 \cdot 10^5$$$; $$$n \cdot m \le 5 \cdot 10^5$$$; $$$q \cdot m \le 5 \cdot 10^5$$$) — 分别是矩阵中的行数和列数以及查询数。

接下来的 $$$n$$$ 行包含 $$$m$$$ 小写拉丁字母 — 矩阵的元素。

以下 $$$q$$$ 行包含查询的描述 — 长度为 $$$m$$$ 的字符串,由拉丁字母的小写字母组成。

输出

打印 $$$q$$$ 整数。第 $$$i$$$ 整数应等于必须执行的最小操作数,以便矩阵包含来自第 $$$i$$$ 查询的字符串,或者如果无法获取指定字符串,则包含 $$$-1$$$。

示例

输入 #1

3 5 4
abacc
ccbba
ccabc
abacc
acbbc
ababa
acbbc

输出 #1

0
2
1
2

输入 #2

6 4 4
daac
bcba
acad
cbdc
aaaa
bcbb
dcdd
acba
bbbb
dbcd

输出 #2

3
1
2
-1

输入 #3

5 10 5
ltjksdyfgg
cbhpsereqn
ijndtzbzcf
ghgcgeadep
bfzdgxqmqe
ibgcgzyfep
bbhdgxqmqg
ltgcgxrzep
ljnpseldgn
ghhpseyzcf

输出 #3

5
3
5
-1
3