Description

The newbie problem setter collected $n$ quotes from a certain expert, and numbered them by time as $1...n$.

He found that this expert’s catchphrase changes over time, and there is also some content that is hard to understand.

After asking the group “DS” master (can also be left as “DS” in pinyin), he got a certain hash method that turns these quotes into binary strings, which seems easier to understand.

To study the secrets of group chatting, he asked many queries: among all quotes between $[l,r]$, what is the length of the longest common substring?

The problem setter knows this is not an easy problem, so he is not in a hurry to get the answer to each query immediately.

Input Format

The first line contains two integers $n,m$, representing the number of quotes and the number of queries.

In the next $n$ lines, the $i$-th line describes the $i$-th quote. The alphabet is guaranteed to be $\{0,1\}$.

In the following $m$ lines, each line contains two integers $l,r(1\leq l<r \leq n)$, representing a query.

Output Format

For each query, output the length of the longest common substring among all quotes between $[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

Hint

For subtask 4: after the quotes are generated, the order between them is randomly shuffled.

For subtask 5: the memory limit is $\texttt{128Mb}$, and for the other testdata it is $\texttt{500Mb}$.

Translated by ChatGPT 5