Paw-Covered Chant

Time limit: 2000 msMemory limit: 256 MB

Gats is practicing a fish-call pattern, but he keeps covering part of it with his paw.

You are given a string $S$ written along the floor and a pattern string $P$ . For a starting position $X$ , Gats compares $P$ with the length- $M$ piece $S_XS_{X+1}\ldots S_{X+M-1}$ .

For a paw width $W$ , Gats may choose exactly $W$ consecutive positions of $P$ and cover them. Covered positions are considered matching no matter what letters are in $S$ . All uncovered positions must match exactly.

More formally, a starting position $X$ is good for $W$ if there exists an integer $A$ with $1 \le A \le M - W + 1$ such that for every integer satisfying and either or , the equality

S_{X+j-1} = P_j

holds.

For each queried paw width $W_t$ , count how many starting positions $X$ are good for $W_t$ .

Input

The first line contains integers $N$ , $M$ , and $Q$ ( $1 \le M \le N \le 2 \times 10^5$ , ), the length of , the length of , and the number of queries.

Output

For each query $t$ , print one integer: the number of starting positions $X$ with $1 \le X \le N - M + 1$ that are good for .

Samples

Sample 1

Input

9 3 3
abzabcaxc
abc
1
2
3

Output

3
3
7

For $W = 1$ , the good starting positions are $X = 1$ , $X = 4$ , and $X = 7$ . For , every possible starting position is good.

Paw-Covered Chant

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2