Anihc country aims to improve the level of social productivity and implement the people-centered development philosophy. It has decided to carry out supply-side structural reform.
To improve the quality of supply, you have investigated the balance of supply and demand in a certain industry over the last $n$ periods. Each period is represented by a digit, either $0$ or $1$, resulting in a $01$ string $S$ of length $n$. To better understand this data, you need to solve some queries. Let $\operatorname{data}(l, r)$ denote the length of the longest common prefix of the two suffixes that have the longest common prefix among all suffixes of $S$ starting at positions in the range $[l, r]$.
For each query $L, R$, calculate:
$$ \mathit{ans} = \sum\limits_{ L \le i \lt R } \operatorname{data}(i, R) $$
Since you actually had no time to conduct the investigation, the data is fabricated; that is, each bit in the string $S$ is generated randomly between $0$ and $1$.
Input
The first line contains two integers $n$ and $Q$, representing the length of the string and the number of queries, respectively.
The next line contains a $01$ string $S$ of length $n$.
The next $Q$ lines each contain two integers $L$ and $R$, representing a query $L, R$.
Output
Output $Q$ lines, each containing an integer representing the answer to the corresponding query.
Examples
Input 1
6 3 010110 2 5 1 6 1 2
Output 1
4 6 0
Subtasks
| Data Point | $n$ Scale | $Q$ Scale |
|---|---|---|
| $1$ | $n \le 20$ | $Q \le 20$ |
| $2$ | ||
| $3$ | $n \le 100$ | $Q \le 100$ |
| $4$ | ||
| $5$ | $n \le 5000$ | $Q \le 5000$ |
| $6$ | ||
| $7$ | $n \le 100\,000$ | $Q \le 100\,000$ |
| $8$ | ||
| $9$ | ||
| $10$ |
For all data, it is guaranteed that $n \le 100\,000$, $Q \le 100\,000$, $1 \le L < R \le n$, and the $01$ string is generated randomly.