# KILO 2018 3/5

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

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
• $1 \leq n \leq 10^{5}$
• $1 \leq m \leq 10^{5}$
• the total length of the $m$ words is at most $10^{6}$
• all letters are lowercase English letters ($a \dots z$)
Example

Input:
 3 3 aab aa ba bb

Output:
0 1 2

Explanation:
• With letters $a$ (one $a$), you cannot form any words.
• With letters $aa$ (two $a$'s), you can form $aa$, but not $ba$ or $bb$ since there are no $b$'s.
• With letters $aab$ (two $a$'s and one $b$), you can form both $aa$ and $ba$, but not $bb$, since there is only one $b$.