Suffix Pair Longest Common Prefix Sum

You are given a binary string \(S\) of length \(n\) representing the supply-demand balance in \(n\) periods. Each character of \(S\) is either 0 or 1.

For any interval \([L,R]\) (using 1-indexing), define \(\mathrm{data}(L,R)\) as follows: consider all suffixes of \(S\) starting at positions in \([L,R]\). Among all pairs of these suffixes, let \(\mathrm{data}(L,R)\) be the length of the longest common prefix (LCP) of the pair which has the maximum LCP among all pairs. (Note that if the interval contains only one suffix then \(\mathrm{data}(L,R)=0\)).

You are given several queries. Each query is specified by two integers \(L\) and \(R\) (with \(L < R\)). For each query, you need to compute: \[ ans = \sum_{i=L}^{R-1} \mathrm{data}(i,R). \]

Explanation: For each query with bounds \(L\) and \(R\), you need to consider for every \(i\) in \([L, R-1]\) the value \(\mathrm{data}(i,R)\) which is defined as the maximum LCP length among any two suffixes starting at positions in \([i, R]\). Then, output the sum of these values.

All formulas are shown in \(\LaTeX\) format.

inputFormat

The first line contains two space-separated integers \(n\) and \(q\) — the length of the binary string and the number of queries respectively.

The second line contains a binary string \(S\) of length \(n\) (each character is either 0 or 1).

Each of the next \(q\) lines contains two space-separated integers \(L\) and \(R\) (&(1 \le L < R \le n)\), representing a query.

outputFormat

For each query, output a single integer representing the sum:

[ ans = \sum_{i=L}^{R-1} \mathrm{data}(i,R), ]

where \(\mathrm{data}(i,R)\) is defined as above.

sample

5 2
10101
1 3
2 5

3
7