Longest Common Subsequence Queries

You are given a list of citizen IDs and a list of query strings. For each query string, you need to compute the length of the longest common subsequence (LCS) between the query string and each citizen ID. The longest common subsequence (LCS) between two strings is defined as the longest sequence that can be derived from both strings by deleting some or no characters without changing the order of the remaining characters. Formally, if you have two strings \(S_1\) and \(S_2\), their LCS is a sequence \(L\) such that \(L\) is a subsequence of both \(S_1\) and \(S_2\) and the length of \(L\) is maximized.

Note: You must read the input from standard input and write the output to standard output.

inputFormat

The first line of input contains two integers \(N\) and \(Q\) separated by a space, where \(N\) is the number of citizen IDs and \(Q\) is the number of queries.

The next \(N\) lines each contain a citizen ID (a non-empty string).

The following \(Q\) lines each contain a query string.

outputFormat

For each query string, output the length of the longest common subsequence between the query and each citizen ID. The results should be printed in order, one per line. The order is determined by iterating through each query in the given order, and for each query, iterating through all citizen IDs in the given order.

## sample

3 2
abcd
efgh
ijkl
ab
ef

2
0
0
0
2
0

</p>