Evaluating Cow Name Energy

Farmer John wants to evaluate the energy of his cows' names. Each cow's name is a non-empty string containing at most 1000 characters. He also has a table of M energy strings (each non-empty and no longer than 30 characters). A cow's name earns 1 energy point for each energy string that appears as a subsequence in the name.

A string A is a subsequence of string B if all the characters of A appear in B in the same order (not necessarily consecutively). All comparisons are case-insensitive, meaning that uppercase and lowercase letters are considered equivalent.

For example, the name "Bessie" contains the energy strings "Be" and "si" (among others) but does not contain "eB". Your task is to compute the energy points for each cow's name.

inputFormat

The first line contains two integers N and M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 100). The next N lines each contain a cow's name (a non-empty string of at most 1000 characters). The following M lines each contain an energy string (a non-empty string of at most 30 characters).

Note: All strings are case-insensitive.

outputFormat

Output N lines. The i-th line should contain a single integer representing the energy (quality points) of the i-th cow's name.

sample

3 2
Bessie
Elsie
Molly
Be
si

2
1
0