题目背景

温馨提示 : 请注意本题特殊的时空限制。

（若您认为使用了复杂度正确的算法但被卡常，可以联系出题人）

一个悠闲的午后，机房里的大佬们都在水群。

题目描述

蒟蒻出题人收集了某位大佬的 $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]$ 之间的所有语录最长公共子串的长度。

3 3
10111
1111010111
010111111101
1 3
1 2
2 3

5
5
6

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

1
6
9
6
10
6
2
1
1
5

提示

对于subtask4 : 语录生成后，之间的顺序经过随机打乱。

对于subtask5 : 空间限制为$\texttt{128Mb}$，其他的数据为$\texttt{500Mb}$。