8538: Hacker

NIO is a hacker who likes to crack passwords for fun.

But one day he forgot his password. He quickly listed some vague clues. There is a lowercase string A of length n and k lowercase strings B₁,…,B_k of length m. Given a uniform weight v₁,…,v_m represents the weight of each position of any B_i.

 
To figure out his password, for all B_i, he wants to find its maximum interval weight sum, and the string formed by this interval is a substring of A(An empty interval represents an empty string, which is legal).

The first line contains three positive integers n,m,k(n,m,k≤10⁵,m∗k≤10⁶).
The second line contains a string A of length n.
The third line contains m integers v_i(−10⁹≤vi≤10⁹).
The next k lines represent the string {B_i}.

k lines for k answers.

10 8 5
aepeihmkkz
0 -3 2 -4 -5 2 -5 5
epesxnud
epeihmkk
peihmrgo
epeihqvy
eppjkuaz

2
5
2
2
5

For B₁, the interval [3,3] forms the string 'e' is a substring of A and the interval sum is 2. Although the interval [1,3] forms the string 'epe' is also a substring of A, but the interval sum is -1 less than 2.