Hacker
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

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 of length m. Given a uniform weight 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 .

The second line contains a string A of length n.

The third line contains m integers .

The next k lines represent the string .

输出描述:

k lines for k answers.
示例1

输入

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

输出

复制
0
8
8
0
8
示例2

输入

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

输出

复制
2
5
2
2
5

说明

For B_1, 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.