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.