You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

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

输入格式

从 substring.in 文件读入数据。

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

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

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

输出格式

输出到 substring.out 文件。

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

样例

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

3
1
7
5
8

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

1
3
8
5
1

样例3

此样例满足 $70\%$ 数据点范围限制。

点击链接 ex_substring3.in 和 ex_substring3.out 下载大样例 3 的输入数据和输出数据。

样例4

此样例满足 $100\%$ 数据点范围限制。

点击链接 ex_substring4.in 和 ex_substring4.out 下载大样例 4 的输入数据和输出数据。

说明/提示

$70\%$ 的数据，$n \le 100,q \le 100$。

$100\%$ 的数据，$n \le 3000,q \le 20000$。