Code Submission Evaluation System Login

KILO 2018 3/5

Start:2018-09-20 16:30:00
End:2018-09-20 18:30:00
 

Tasks | Scoreboard | Statistics


CSES - KILO 2018 3/5 - Alphabet AccumulationCSES - Alphabet Accumulation

Alphabet Accumulation

Time limit:2.00 s
Memory limit:512 MB

You are given a string $s$ of length $n$ and a list of $m$ words. Your task is to calculate for each prefix of $s$ the number of words that can be formed using its letters.

For example, if the prefix is $aab$ and the words are $aa$, $ba$, $bb$, you can form both $aa$ and $ba$, since there are two $a$'s and one $b$, but not $bb$, since there is only one $b$.

Input

The first line contains two integers $n$ and $m$: the length of $s$ and the words in the list. The second line contains a string $s$ of length $n$. Finally, there are $m$ lines, each containing a word.

Output

Output $n$ integers, where the $i$'th is the amount of words that can be formed using the letters in the prefix of length $i$ of $s$.

Constraints
Example

Input:

3 3
aab
aa
ba
bb


Output:
0 1 2

Explanation: