Longest Common Substring in Binary Quotes

A famous figure has n memorable quotes (ordered chronologically from 1 to n). After applying a special hash method, each quote is converted into a binary string (i.e. a string of 0s and 1s).

You are given these n binary strings. Then, you will be asked m queries. Each query is represented by two integers l and r and asks: what is the length of the longest common substring (i.e. contiguous subsequence) among all quotes with indices in the range [l,r]?

In mathematical terms, let there be binary strings \(S_1,S_2,\dots,S_n\). For a given query \([l,r]\), you need to compute:

\[ L = \max \{ k \mid \exists\,x\; s.t. \; \forall i \in [l,r],\; x \text{ is a substring of } S_i \} \]

Note that if no non-empty common substring exists among the selected strings, then the answer is 0.

inputFormat

The first line contains two integers n and m, the number of binary strings and the number of queries, respectively.

The following n lines each contain a binary string. It is guaranteed that each string is non-empty, and consists only of characters '0' and '1'.

Then, the next m lines each contain two integers l and r (1-indexed), representing a query.

outputFormat

For each query, output a single line containing one integer: the length of the longest common substring among all the binary strings from index l to index r.

sample

3 2
1010
110
10
1 2
1 3

2
2

</p>