提示: 欢迎访问OurACM平台。
Problem 1632 Word Power

Accept: 199    Submit: 598
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Farmer John wants to evaluate the quality of the names of his N (1 <= N <= 1000) cows. Each name is a string with no more than 1000 characters, all of which are non-blank.
He has created a set of M (1 <= M <= 100) 'good' strings (no longer than 30 characters and fully non-blank). If the sequence letters of a cow's name contains the letters of a 'good' string in the correct order as a subsequence (i.e., not necessarily all next to each other), the cow's name gets 1 quality point.
All strings is case-insensitive, i.e., capital letters and lower case letters are considered equivalent. For example, the name "Bessie" contains the letters of "Be", "sI", "EE", and "Es" in the correct order, but not "is" or "eB". Help Farmer John determine the number of quality points in each of his cow's names.

Input

There are multiple tests. For each test, there are three parts.
  • * Line 1: Two space-separated integers: N and M
  • * Lines 2..N+1: Line i+1 contains a string that is the name of the ith cow
  • * Lines N+2..N+M+1: Line N+i+1 contains the ith good string

Output

For each test, you should output following part.
* Lines 1..N+1: Line i+1 contains the number of quality points of the ith name

Sample Input

5 3 Bessie Jonathan Montgomery Alicia Angola se nGo Ont

Sample Output

1 1 2 0 1

Source

Summer Training Qualification II

Submit  Back  Status  Discuss