题目描述

雪豹得到一个字符串，在给定 $m$ 个区间，每个询问包含两个整数 $l, r$，请你判断这 $m$ 个询问所包含的字符串子串有多少种。

输入格式

第一行包含整数 $n$ 和 $m$，表示字符串长度和询问次数。

第二行包含一个长度为 $n \: (1 \leq n \leq 2 \times 10^5)$ 的字符串，字符串中只包含大小写英文字母和数字。

接下来 $m$ 行，每行包含两个整数 $l, r \: (1 \leq l \leq r \leq n)$ 表示一次询问所涉及的一个区间。

输出格式

输出一个整数，表示在 $m$ 个询问当中有多少个不同的子串。

输入输出样例

14 4
woxuebaoxuebao
1 3
3 5
9 11
1 14

3

提示

注意，字符串的位置从 $1$ 开始编号。