子串的子串

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

小 Z 有一个只包含小写英文字母的字符串 $s$，下标从 $1$ 开始。定义 $f(s)$ 为字符串 $s$ 中不同子字符串的数量。

现在有 $q$ 次询问，每次询问需要回答 $f(s[l\ldots r])$ 的值，其中 $s[l\ldots r]$ 表示字符串 $s$ 下标从 $l$ 开始到 $r$ 结束的子串。

输入格式

第一行输入两个整数 $n,q$，分别表示字符串的长度和询问的次数。

第二行输入一个只包含小写英文字母的字符串 $s$。

接下来有 $q$ 行，每行包含两个整数 $l,r$（$1 \le l \le r \le n$），表示一次询问。

输出格式

对于每次询问，输出一行一个整数表示答案。

样例输入 1

5 5
bbaba
3 4
2 2
2 5
2 4
1 4

样例输出 1

3
1
7
5
8

样例输入 2

5 5
baaba
3 3
3 4
1 4
3 5
5 5

样例输出 2

1
3
8
5
1

数据范围

对于所有数据，$1\le n\le 3000$，$1\le q\le 20000$，$1\le l\le r\le n$，字符串 $s$ 只包含小写英文字母。