For a string $S$, we define $|S|$ as the length of $S$. Next, we define $S_i$ as the $i$-th character of $S$, and $S_{L,R}$ as the string formed by concatenating the characters of $S$ from the $L$-th position to the $R$-th position (inclusive, counting from left to right). Specifically, if $L > R$, or $L \notin [1, |S|]$, or $R \notin [1, |S|]$, we consider $S_{L,R}$ to be an empty string.
Given a string $S$ of length $n$ consisting only of digits, there are $q$ queries. For the $k$-th query, you are given a substring $S_{l,r}$. Please find the number of pairs $(i, j)$ such that $1 \le i < j \le n$, $i + 1 < j$, and $S_{l,r}$ appears in $S_{1,i}$, or in $S_{i+1, j-1}$, or in $S_{j,n}$.
Input
The first line contains two integers $n, q$. The second line contains a string $S$ of length $n$ consisting only of digits. The next $q$ lines each contain two positive integers $l$ and $r$, representing the substring $S_{l,r}$ for that query.
Output
For each query, output a single integer representing the number of valid pairs.
Subtasks
| Test Case | $n$ | $q$ | Other Constraints | ||
|---|---|---|---|---|---|
| 1 | $= 50$ | $= 100$ | None | ||
| 2 ~ 3 | $= 300$ | $= 300$ | None | ||
| 4 ~ 5 | $= 2000$ | $= 3000$ | None | ||
| 6 ~ 9 | $= 100000$ | $= 100000$ | $\sum | S_{l,r} | \le 10^6$ |
| 10 ~ 12 | $= 30000$ | $= 50000$ | None | ||
| 13 | $= 100000$ | $= 100000$ | $S$ contains only $0$ | ||
| 14 ~ 20 | $= 100000$ | $= 300000$ | None |
For all test data, $1 \le n \le 10^5$, $1 \le q \le 3 \cdot 10^5$, $1 \le l \le r \le n$.
Examples
Input 1
5 2 00100 1 2 1 3
Output 1
5 1