[CTSC2012]熟悉的文章

题目描述

阿米巴是小强的好朋友。 在小强眼中,阿米巴是一个作文成绩很高的文艺青年。为了获取考试作文的真谛,小强向阿米巴求教。阿米巴给小强展示了几篇作文,小强觉得这些文章怎么看怎么觉得熟悉,仿佛是某些范文拼拼凑凑而成的。小强不禁向阿米巴投去了疑惑的眼光,却发现阿米巴露出了一个狡黠的微笑。 为了有说服力地向阿米巴展示阿米巴的作文是多么让人觉得“眼熟”,小强想出了一个评定作文 “熟悉程度”的量化指标:$L_0$ .小强首先将作文转化成一个 $01$ 串。之后,小强搜集了各路名家的文章,同样分别转化成 $01$ 串后,整理出一个包含了 $M$ 个 $01$ 串的 “ 标准作文库 ”。 小强认为:如果一个 $01$ 串长度不少于 $L$ 且在标准作文库中的某个串里出现过(即,它是标准作文库的某个串的一个 连续子串),那么它是 “ 熟悉 ” 的。对于一篇作文(一个 $01$ 串)$A$,如果能够把 $A$ 分割成若干段子串,其中 “ 熟悉 ” 的子串的长度总和不少于 $A$ 总长度的 $90\%$,那么称 $A$ 是 “ 熟悉的文章 ”。 $L_0$ 是能够让 $A$ 成为 “ 熟悉的文章 ” 的 所有 $L$ 的最大值 (如果不存在这样的 $L$,那么规定 $L_0=0$)。 举个例子: 小强的作文库里包含了如下 $2$ 个字符串: ```cpp 10110 000001110 ``` 有一篇待考察的作文是: ```cpp 1011001100 ``` 小强计算出这篇作文 $L$ 的最大值是 $4$,因为待考察的作文可以视作 $10110+0110+0$,其中 $10110$ 和 $0110$ 被判定为 “熟悉” 的。而当 $L = 5$ 或是更大的时候,不存在符合题意的分割方法。所以,这篇作文的 $L_0 = 4$。小强认为阿米巴作文的 $L_0$ 值比其他同学的明显要大。请你帮他验证一下。

输入输出格式

输入格式


输入第一行是两个整数 $N, M$,表示待检查的作文数量,和小强的标准作文库的行数。 接下来是 $M$ 行的 $01$ 串,表示标准作文库。 接下来是 $N$ 行的 $01$ 串,表示 $N$ 篇作文。

输出格式


输出包含 $N$ 行,每一行包含一个整数,表示该篇作文的 $L_0$ 值。

输入输出样例

输入样例 #1

1 2
10110
000001110
1011001100

输出样例 #1

4

说明

对于 $30\%$ 的测试数据,输入文件的长度不超过 $1000$ 字节。 对于 $50\%$ 的测试数据,输入文件的长度不超过 $61000$ 字节。 对于 $80\%$ 的测试数据,输入文件的长度不超过 $250000$ 字节。 对于 $100\%$ 的测试数据,输入文件的长度不超过 $1100000$ 字节。