Cyclic Shifts
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 2900
Tags: *special, strings

You are given a matrix consisting of $$$n$$$ rows and $$$m$$$ columns. The matrix contains lowercase letters of the Latin alphabet.

You can perform the following operation any number of times you want to: choose two integers $$$i$$$ ($$$1 \le i \le m$$$) and $$$k$$$ ($$$0 < k < n$$$), and shift every column $$$j$$$ such that $$$i \le j \le m$$$ cyclically by $$$k$$$. The shift is performed upwards.

For example, if you have a matrix

$$$\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) $$$

You have to process $$$q$$$ queries. Each of the queries is a string of length $$$m$$$ consisting of lowercase letters of the Latin alphabet. For each query, you have to calculate the minimum number of operations described above you have to perform so that at least one row of the matrix is equal to the string from the query. Note that all queries are independent, that is, the operations you perform in a query don't affect the initial matrix in other queries.

Input format:
The first line contains three integers $$$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$$$) — the number of rows and columns in the matrix and the number of queries, respectively.

The next $$$n$$$ lines contains $$$m$$$ lowercase Latin letters each — elements of the matrix.

The following $$$q$$$ lines contains a description of queries — strings of length $$$m$$$ consisting of lowercase letters of the Latin alphabet.

Output format:
Print $$$q$$$ integers. The $$$i$$$-th integer should be equal to the minimum number of operations you have to perform so that the matrix contains a string from the $$$i$$$-th query or $$$-1$$$ if the specified string cannot be obtained.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Example input:
3 5 4
abacc
ccbba
ccabc
abacc
acbbc
ababa
acbbc

Example output:
0
2
1
2

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

Example output:
3
1
2
-1

Editorial:
There are several solutions to the problem, even unexpected ones, like trie merging. But let's describe the author's solution.
Let's suppose to make the string query $$$t$$$ appear we made $$$k$$$ cyclic shifts of suffixes $$$1 < i_1 < i_2 < \dots < i_k \le m$$$. It equivalent to building $$$t$$$ as concatenation of substrings $$$s_{r_1}[1 \dots i_1 - 1]$$$ from some row $$$r_1$$$, $$$s_{r_2}[i_1 \dots i_2 - 1]$$$ from other row $$$r_2$$$ and so on.
Let's define a string on row $$$r$$$ starting from column $$$c$$$ as $$$s_{r,c}$$$ and character on row $$$r$$$ and column $$$c$$$ as $$$ch_{r,c}$$$.
It's not hard to prove that there is a greedy strategy: at first, you should find such row $$$r_1$$$ that $$$s_{r_1, 1}$$$ and $$$t$$$ has the maximum common prefix (let's name its length as $$$l_1$$$). Then we "cut" this prefix from $$$t$$$ and find $$$r_2$$$ that $$$s_{r_2, 1 + l_1}$$$ and $$$t$$$ has the maximum common prefix and so on. If we found the whole string $$$t$$$ then the answer is the number of segments minus one, otherwise, it's impossible to build $$$t$$$.
The question is how to find these common prefixes. To do it, we can sort all $$$s_{r, c}$$$ in each column $$$c$$$ lexicographically in the following way:
• if $$$c = m$$$, then $$$s_{r,c} = ch_{r, c}$$$, and we can sort strings manually;
• otherwise, we know that $$$s_{r,c} = ch_{r,c} + s_{r, c + 1}$$$, so we assign to $$$s_{r,c}$$$ a pair $$$(ch_{r,c}, \text{index of $$$s_{r, c + 1}$$$ in lexicographical order})$$$ and we can sort these pairs instead.
Now, for starting column $$$c$$$ we need to find the longest common prefix of $$$t$$$ and any $$$s_{i, c}$$$. Since we already sorted $$$s_{i, c}$$$, we know that all strings starting from character $$$t_1$$$ form a segment in it and we can binary search its left and right border $$$[l_1, r_1]$$$. Then all strings starting from two characters $$$t_1 t_2$$$ form a subsegment $$$[l_2, r_2] \subseteq [l_1, r_1]$$$, so we can binary search $$$l_2$$$ and $$$r_2$$$ inside segment $$$[l_1, r_1]$$$.
In other words, we can binary search the first character $$$t_1$$$ in all rows, then binary search the second character $$$t_2$$$ inside the segment $$$[l_1, r_1]$$$ and so on while the segment is not empty. In total, we make $$$O(m)$$$ binary searches per query $$$t$$$ with total complexity $$$O(m \log(n))$$$.
The total complexity is $$$O((n + q)m \log(n))$$$.