We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Strings
  4. Similar Strings

Similar Strings

Jimmy loves playing with strings. He thinks string is similar to string if the following conditions are satisfied:

  • Both strings have the same length (i.e., and ).
  • For each valid pair of indices, , in the strings, and or and .

For example, string and are similar as for , and and for all other pairs as well as .

He has a string, , of size and gives you queries to answer where each query is in the form of a pair of integers . For each substring , find the number of substrings where substring is similar to substring and print this number on a new line.

Note: Substring is the contiguous sequence of characters from index to index . For example, if abcdefgh, then cdef.

Input Format

The first line contains two space-separated integers describing the respective values of and .
The second line contains string .
Each line of the subsequent lines contains two space-separated integers describing the respective values of and for query .

Constraints

Output Format

For each query, print the number of similar substrings on a new line.

Sample Input

8 4
giggabaj
1 1
1 2
1 3
2 4

Sample Output

8
6
2
1

Explanation

We perform the following sequence of queries:

  1. Strings with length are all similar, so our answer is .
  2. gi, ig, ga, ab, ba, and aj are similar, so our answer is .
  3. gig and aba are similar, so our answer is .
  4. igg has no similar string, so our answer is .