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$.