题目描述
Problem Background
Friendly Reminder: Please pay attention to the special time and space limits of this problem.
(If you believe you have used a correct complexity algorithm but are experiencing performance issues, you can contact the problem setter.)
On a leisurely afternoon, the experts in the computer room are all chatting in the group.
Problem Description
The novice problem setter has collected $n$ quotes from a certain expert, numbered in chronological order from $1$ to $n$.
He found that the expert's catchphrase changes over time and contains some incomprehensible content.
After consulting with a group of DS masters, he obtained a certain hash method, which transformed these quotes into 01 strings, making them seem more understandable.
To study the mysteries of group chatting, he conducted multiple queries: What is the length of the longest common substring among all quotes between $[l, r]$?
The problem setter knows this is not a simple problem, so he is not in a hurry to get the answer for each query immediately.
Input Format
The first line contains two integers $n$ and $m$, representing the number of quotes and the number of queries, respectively.
For the next $n$ lines, the $i$-th line represents the $i$-th quote, with the character set guaranteed to be $\{0, 1\}$.
The next $m$ lines each contain two integers $l$ and $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]$.
Sample Input and Output
Sample Input #1
3 3
10111
1111010111
010111111101
1 3
1 2
2 3
Sample Output #1
5
5
6
Sample Input #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
Sample Output #2
1
6
9
6
10
6
2
1
1
5
Notes
| Subtask Number | $\bf n$ | $\bf m$ | Total Length of Quotes | Score |
|---|---|---|---|---|
| 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$ |
For Subtask 4: After the quotes are generated, the order between them is randomly shuffled.
For Subtask 5: The space limit is $\texttt{128Mb}$, while other data have a limit of $\texttt{500Mb}$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分