给定一个由 $$$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