Background

Description

You investigated the supply-demand balance of an industry over the past $n$ periods. Each period is represented by a single digit, either $0$ or $1$. Thus, this forms a $\texttt{01}$ string $S$ of length $n$. To better understand the data, you need to answer several queries. Let $\text{data}(L, R)$ denote: among all suffixes of $S$ whose starting positions lie in $[L, R]$, the length of the longest common prefix of the two suffixes that achieve the maximum common prefix.

For each query $L, R$, compute:

It is guaranteed that each character of $S$ is randomly generated as $0$ or $1$.

Output Format

Output $Q$ lines, each containing a single integer, the answer to the corresponding query.

6 3
010110
2 5
1 6
1 2

4
6
0

Hint

[Constraints and Notes]

For all testdata, it is guaranteed that $n \leqslant 10^5$, $Q \leqslant 10^5$, $1 \leqslant L < R \leqslant n$, and the $\texttt{01}$ string is randomly generated.

Translated by ChatGPT 5