Word Power

Interview

Time limit1sMemory limit128 MB

Summary

For each of N cow names, count how many of M good strings appear as a case-insensitive subsequence of the name.

Level: Medium4 of 10
Topics: String, Two pointers, Implementation, Brute force
Solved: No attempts yet

Problem

Farmer John wants to measure the quality of the names of his $N$ ( $1 \le N \le 1000$ ) cows. Each name is a string of at most 1000 characters, all of which are non-blank.

He has also prepared a set of $M$ ( $1 \le M \le 100$ ) "good" strings, each at most 30 characters long and fully non-blank. A cow's name earns 1 quality point for every good string whose letters appear, in order, as a subsequence of the name — the matched letters do not have to be adjacent.

All comparisons are case-insensitive: uppercase and lowercase letters are treated as equal. For example, the name "Bessie" contains "Be", "sI", "EE", and "Es" in order, but not "is" or "eB".

Help Farmer John determine the number of quality points for each cow's name.

Input

Line 1: Two space-separated integers, $N$ and $M$ .
Lines 2 to $N+1$ : Line $i+1$ contains the name of the $i$ -th cow.
Lines $N+2$ to $N+M+1$ : Line $N+i+1$ contains the $i$ -th good string.

Output

Lines 1 to $N$ : Line $i$ contains the number of quality points of the $i$ -th cow's name.

Hint

In the sample there are 5 cows named "Bessie", "Jonathan", "Montgomery", "Alicia", and "Angola", together with the 3 good strings "se", "nGo", and "Ont".

"Bessie" contains "se"; "Jonathan" contains "Ont"; "Montgomery" contains both "nGo" and "Ont"; "Alicia" contains none of the good strings; and "Angola" contains "nGo".

Examples3

Example 1

Input

5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
se
nGo
Ont

Expected output

Example 2
Input
```
1 1
abc
abc
```
Expected output
```
1
```
Example 3
Input
```
1 3
AbCdEf
ace
BDF
XYZ
```
Expected output
```
2
```