Description

For a string $s$, define $|s|$ to denote the length of $s$.

Next, define $s_i$ as the $i$-th character of $s$, and $s_{l,r}$ as the string formed by concatenating, from left to right, the $l$-th through the $r$-th characters of $s$. In particular, if $l \gt r$, or $l \notin [1, |s|]$, or $r \notin [1, |s|]$, we consider $s_{l,r}$ to be the empty string.

Given a string $s$ of length $n$ consisting only of digits, there are $q$ queries. In the $k$-th query, a substring $s_{l,r}$ of $s$ is given. For this substring, count the number of pairs $(i, j)$ such that $1 \le i \lt j \le n$, $i + 1 < j$, and $s_{l,r}$ occurs in $s_{1,i}$ or in $s_{i+1,j-1}$ or in $s_{j,n}$.

Input Format

The first line contains two integers, the string length $n$ and the number of queries $q$.

The second line contains a string of length $n$ consisting only of digit characters, representing $s$.

Each of the next $q$ lines contains two positive integers $l$ and $r$, indicating that the queried substring is $s_{l,r}$.

Output Format

For each query, output a single integer on its own line representing the answer.

5 2
00100
1 2
1 3

5
1

Hint

For all testdata, $1 \le n \le 10^5$, $1 \le q \le 3 \times 10^5$, $1 \le l \le r \le n$, and $s$ contains only digit characters.

Translated by ChatGPT 5