Description

Amiba is Xiao Qiang’s good friend.

In Xiao Qiang’s eyes, Amiba is a literary youth with excellent essay scores. To grasp the essence of exam essays, Xiao Qiang asked Amiba for guidance. Amiba showed him several essays. Xiao Qiang felt they looked very familiar, as if they were pieced together from some model essays. He cast a doubtful look at Amiba, only to see a sly smile.

To convincingly show how “familiar” Amiba’s essays feel, Xiao Qiang devised a quantitative metric for the “degree of familiarity” of an essay: $L_0$. He first converts an essay into a $01$ string. Then he collects essays from various famous authors, also converts them into $01$ strings, and compiles a “standard essay library” containing $M$ $01$ strings.

Xiao Qiang considers the following: if a $01$ string has length at least $L$ and appears in some string in the standard essay library (i.e., it is a contiguous substring of some string in the library), then it is “familiar.” For an essay (a $01$ string) $A$, if we can split $A$ into several substrings such that the total length of the “familiar” substrings is at least $90\%$ of the total length of $A$, then $A$ is a “familiar article.” $L_0$ is the maximum among all $L$ that make $A$ a “familiar article” (if no such $L$ exists, define $L_0 = 0$).

For example:

Xiao Qiang’s essay library contains the following $2$ strings:

10110
000001110

There is an essay to be examined:

1011001100

Xiao Qiang computes that the maximum $L$ for this essay is $4$, because the essay can be viewed as $10110+0110+0$, where $10110$ and $0110$ are judged “familiar.” When $L = 5$ or larger, no valid split exists. Therefore, this essay’s $L_0 = 4$. Xiao Qiang believes that Amiba’s $L_0$ values are noticeably larger than other students’. Please help him verify this.

Input Format

The first line contains two integers $N, M$, denoting the number of essays to check and the number of strings in Xiao Qiang’s standard essay library.

The next $M$ lines contain $01$ strings, forming the standard essay library.

The next $N$ lines contain $01$ strings, representing the $N$ essays.

Output Format

Output $N$ lines. Each line contains one integer, the $L_0$ value of the corresponding essay.

1 2
10110
000001110
1011001100

4

Hint

For $30\%$ of the testdata, the input file length does not exceed $1000$ bytes.

For $50\%$ of the testdata, the input file length does not exceed $61000$ bytes.

For $80\%$ of the testdata, the input file length does not exceed $250000$ bytes.

For $100\%$ of the testdata, the input file length does not exceed $1100000$ bytes.

Translated by ChatGPT 5