题意
给定一个长度为 $n$ 的串 $S$。 定义 $occ(T)$ 表示串 $T$ 在 $S$ 中出现的次数。 $q$ 次询问，每次询问给定一个区间 $[l, r]$，查询 $S[l, r]$ 的所有子串的 $occ$ 之和。
输入格式
第一行一个整数 $n$。
第二行一个长度为 $n$ 的串 $S$。
第三行一个整数 $q$。
接下来 $q$ 行，每行两个整数 $l, r$ 表示一组询问。
输出格式
对于每个询问，输出一行一个整数表示答案。
样例输入
5
abaab
3
1 2
2 4
1 5样例输出
7
11
25数据范围
$1 \leq n, q \leq 2 \times 10^5$，字符集为小写字母。