P5576 [CmdOI2019] Catchphrase

**Friendly reminder**: Please note the special time and memory limits of this problem. (If you believe you used an algorithm with the correct complexity but it fails due to constant factors, you can contact the problem setter.) On a leisurely afternoon, the experts in the computer room are all chatting in groups.

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.

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

For each query, output the length of the longest common substring among all quotes between $[l,r]$.

| Subtask ID | $\bf n$ | $\bf m$ | Total quote length | 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 memory limit is $\texttt{128Mb}$, and for the other testdata it is $\texttt{500Mb}$. Translated by ChatGPT 5