[CmdOI2019] 口头禅

题目背景

**温馨提示** : 请注意本题特殊的时空限制。 (若您认为使用了复杂度正确的算法但被卡常,可以联系出题人) 一个悠闲的午后,机房里的大佬们都在水群。

题目描述

蒟蒻出题人收集了某位大佬的 $n$ 条语录,并按时间为序编号为 $1...n$ 。 他发现这位大佬的口头禅是随着时间而变化的,而且里面有些看不懂的内容。 在请教了群 DS 带师之后,他得到了某种 hash 方法,把这些语录都变成了 01 串,这样似乎好懂一些。 为了研究水群的奥秘,他进行了多次询问 : $[l,r]$ **之间的所有语录,最长公共子串的长度是多少**? 出题人知道这并不是一个简单的问题,所以他并不急于即时得知每个询问的答案。

输入输出格式

输入格式


第一行两个整数 $n,m$ ,表示语录的条数和询问个数。 对于后 $n$ 行,第 $i$ 行表示第 $i$ 条语录,保证字符集为 $\{0,1\}$。 后 $m$ 行,每行两个整数 $l,r(1\leq l<r \leq n)$ ,表示一个询问。

输出格式


对于每个询问,输出 $[l,r]$ 之间的所有语录最长公共子串的长度。

输入输出样例

输入样例 #1

3 3
10111
1111010111
010111111101
1 3
1 2
2 3

输出样例 #1

5
5
6

输入样例 #2

10 10
00
010
1000000001
1000000110000001
00010100110101001011000110100001
10111001001010100100000011011
101110010010101001000000101011
1011100100101010010010000111011
1011100100101010011010000101011
0001101001101011
1 4
6 10
5 6
4 6
9 10
7 10
2 10
1 5
1 8
4 7

输出样例 #2

1
6
9
6
10
6
2
1
1
5

说明

| subtask编号 |  $\bf n$  |  $\bf m$  | 语录总长 | 分值 | | :--: | :--: | :--: | :--: | :--: | | 1 | $50$ | $50$ | $500$ | $10$ | | 2 | $50$ | $50$ | $8\times 10^4$ | $15$ | | 3 | $2000$ | $10^4$ | $1.6\times 10^5$ | $15$ | | 4 | $2\times 10^4$ | $10^5$ | $4\times 10^5$ | $15$ | | 5 | $2\times 10^4$ | $10^5$ | $4\times 10^5$ | $45$ | 对于subtask**4** : 语录生成后,**之间**的顺序经过随机打乱。 对于subtask**5** : 空间限制为$\texttt{128Mb}$,其他的数据为$\texttt{500Mb}$。