Homework Farming

You are given a lowercase English string $S$ of length $N$. A string $T$ is initially empty.

There are $Q$ assignments in order. Immediately before the $i$-th assignment, append the first $a_i$ characters of $S$ to the end of $T$. Then find the number of occurrences of as a contiguous substring of the current .

Overlapping occurrences are all counted.

Find the answer for every assignment.

The input is given in the following format.

$N\ Q$ $S$ $a_1\ a_2\ \cdots\ a_Q$

Print $Q$ lines. The $i$-th line must contain the answer to the $i$-th assignment.

• $1 \le N,Q \le 200\,000$.
• $S$ is a lowercase English string of length $N$.
• $1 \le a_i \le N$ ().