Secret Binary Prefix Matching

Bessie is leading the cows in an attempt to escape! The cows are sending secret binary messages, and Farmer John has intercepted the first bits of each of these messages. In addition, he knows a list of partial codewords (also binary strings) that the cows might be using.

For each intercepted message you are given its first b_i bits, and for each codeword you are given its first c_j bits. A message and a codeword are said to match if their first min(b_i,c_j) bits are identical. In other words, they match if one string is a prefix of the other.

Your task is to compute, for each codeword, the number of intercepted messages that match it.

Constraints:

• \(1 \le M \le 50000\): the number of intercepted messages
• \(1 \le N \le 50000\): the number of codewords
• \(1 \le b_i, c_j \le 10000\) for each message and each codeword
• The total number of bits \(\sum b_i + \sum c_j\) does not exceed \(500000\).

Input Format (detailed below): The first line contains two integers M and N. The following M lines each contain a binary string representing the intercepted message (its known prefix). This is followed by N lines each containing a binary string representing a codeword (its known prefix).

Output Format: For each codeword (in the same order as input), output a single integer on a new line – the number of intercepted messages that match the codeword.

inputFormat

The first line contains two space-separated integers M and N.

The next M lines each contain a binary string representing an intercepted message.

The following N lines each contain a binary string representing a codeword.

outputFormat

Output N lines, each containing a single integer: the number of intercepted messages that match the corresponding codeword. Two strings match if their first \(\min(|message|,|codeword|)\) bits are identical.

sample

3 3
101
11
001
1
10
00

2
1
1