There is a string and questions.

For each question , please print the number of distinct substrings who at least once end in the range .

We called a substring's end positions are the positions it ends in the string.

输入描述:

The first line contains two integers  (), indicating the length of the string  and the number of questions.

The second line contains a string  with length  containing only lowercase English letters.

In each of the next  lines, there are two integers () describing a question.

输出描述:

 lines in total, each line should contain only one integer - the answer to the corresponding question.

6 6
aaaaaa
1 2
1 3
1 4
1 5
1 6
4 6

2
3
4
5
6
6

14 3
znloveloveqcjj
1 14
3 11
2 10

94
53
44

备注:

The index of a string in this problem starts from .

A substring of  can be obtained by removing zero or more(but not all) characters from the beginning and the end of .