The following languages are only available languages for the problems from the contest

Kotlin Heroes 5: ICPC Round:

- Kotlin 1.4.31

No tag edit access

The problem statement has recently been changed. View the changes.

×
I. Cyclic Shifts

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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

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

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

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.

Examples

Input

3 5 4 abacc ccbba ccabc abacc acbbc ababa acbbc

Output

0 2 1 2

Input

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

Output

3 1 2 -1

Input

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

Output

5 3 5 -1 3

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/03/2022 11:22:50 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|