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 of length and lowercase strings of length . Given a uniform weight represents the weight of each position of any .

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

The first line contains three positive integers .

The second line contains a string  of length .

The third line contains  integers .

The next  lines represent the string .

 lines for  answers.

5 5 5
uqusa
-9 -7 8 -8 -3
saimh
qusam
qusaf
ubgxj
uquxw

0
8
8
0
8

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

2
5
2
2
5

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