I. Циклические сдвиги
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана матрица, состоящая из $$$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) $$$

и вы выполните операцию с $$$i = 2$$$, $$$k = 1$$$, тогда матрица станет равна:

$$$\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$$$, если заданную строку невозможно получить.

Примеры
Входные данные
3 5 4
abacc
ccbba
ccabc
abacc
acbbc
ababa
acbbc
Выходные данные
0
2
1
2
Входные данные
6 4 4
daac
bcba
acad
cbdc
aaaa
bcbb
dcdd
acba
bbbb
dbcd
Выходные данные
3
1
2
-1
Входные данные
5 10 5
ltjksdyfgg
cbhpsereqn
ijndtzbzcf
ghgcgeadep
bfzdgxqmqe
ibgcgzyfep
bbhdgxqmqg
ltgcgxrzep
ljnpseldgn
ghhpseyzcf
Выходные данные
5
3
5
-1
3