The UTPC officers have arrived in Albuquerque just in time for the annual balloon fiesta! They have finally purchased a camera so that they can take photos of the balloons.
The balloons are just about to take off, and $$$n$$$ of them are currently arranged in a row, numbered from $$$1$$$ to $$$n$$$ in left to right order. By chance, each balloon consists of a single color that is represented by a lowercase English letter, and the entire row of balloons is represented by a string $$$s$$$ of length $$$n$$$. Moreover, the $$$i$$$-th balloon consists entirely of the color $$$s_i$$$, and if two balloons have the same color, they appear identical.
Mark has taken $$$q$$$ photos, each of a subsequence of consecutive balloons. The $$$j$$$-th photo is represented by $$$l_j$$$ and $$$r_j$$$, indicating that the $$$j$$$-th photo is the substring $$$s[l_j...r_j]$$$ where $$$s[a...b]$$$ denotes the substring of $$$s$$$ from index $$$a$$$ to index $$$b$$$ (both inclusive). Dylan took a single photo of the entire row of balloons.
The following day, Dylan is viewing Mark's photos and for each one he is curious as to how many of the $$$n$$$ balloons could have been in the photo. Balloon $$$i$$$ could be in the $$$j$$$-th photo if index $$$i$$$ is contained in a substring of $$$s$$$ that is equal to $$$s[l_j...r_j]$$$. More formally, balloon $$$i$$$ could be in the photo if there exists $$$a \in [1, n + l_j - r_j]$$$ such that $$$s[a...a+r_j-l_j] = s[l_j...r_j]$$$, and $$$a \leq i \leq a + r_j - l_j$$$. Please help Dylan, and for each of Mark's photos, output the number of balloons that could have appeared in the photo!
The first line of input consists of integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — denoting the number of balloons in the row and the number of photos taken by Mark respectively.
The second line of input consists of a string $$$s$$$ of $$$n$$$ lowercase English characters, where $$$s_i$$$ denotes the color of the $$$i$$$-th balloon in the row.
The $$$j$$$-th of the next $$$q$$$ lines consists of integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$) — denoting the leftmost and rightmost balloons included in the $$$j$$$-th of Mark's photos.
Output $$$q$$$ integers each on their own line, representing the number of balloons that could have appeared in each of Mark's photos.
12 3abcabbcababa1 27 98 10
8 6 5
The first photo that Mark took is $$$s[1...2] = \text{ab}$$$. The $$$8$$$ balloons that could appear in the photo are balloons $$$1$$$ (in $$$s[1...2]$$$), $$$2$$$ (in $$$s[1...2]$$$), $$$4$$$ (in $$$s[4...5]$$$), $$$5$$$ (in $$$s[4...5]$$$), $$$8$$$ (in $$$s[8...9]$$$), $$$9$$$ (in $$$s[8...9]$$$), $$$10$$$ (in $$$s[10...11]$$$), and $$$11$$$ (in $$$s[10...11]$$$).
The second photo that Mark took is $$$s[7...9] = \text{cab}$$$. The $$$6$$$ balloons that could appear in the photo are balloons $$$3$$$ (in $$$s[3...5]$$$), $$$4$$$ (in $$$s[3...5]$$$), $$$5$$$ (in $$$s[3...5]$$$), $$$7$$$ (in $$$s[7...9]$$$), $$$8$$$ (in $$$s[7...9]$$$), and $$$9$$$ (in $$$s[7...9]$$$).
The third photo that Mark took is $$$s[8...10] = \text{aba}$$$. The $$$5$$$ balloons that could appear in the photo are balloons $$$8$$$ (in $$$s[8...10]$$$), $$$9$$$ (in $$$s[8...10]$$$), $$$10$$$ (in $$$s[8...10]$$$ and $$$s[10...12]$$$), $$$11$$$ (in $$$s[10...12]$$$), and $$$12$$$ (in $$$s[10...12]$$$).
